* {$T(N) <= T(N - 1) + Probabilitate( P nu apartine C{~I - {P},B~} ) * O(N)$} + O(1)
Primul termen din partea dreapta a inegalitatii reflecta numarul de operatii folosite de apelul recursiv MINCIRCLE{$(I - {P}, B)$}, iar al doilea termen reflecta numarul de operatii folosite pentru cazurile in care {$P$} nu apartine cercului {$C$}.

Datorita alegerii punctelor in mod random in timpul calcularii lui {$C{~I,B~}$}, fiecare punct din {$I$} are probabilitatea {$^1^/{~N~}$} de a fi ales. Datorita faptului ca exista cel mult 3 puncte care se vor afla in exteriorul cercului {$C{~I - {P},B~}$} pentru orice set I de puncte, probabilitatea ca {$P$} sa nu apartina cercului {$C{~I - {P},B~}$} este egala cu {$^3^/{~N~}$}. Astfel inegalitatea de mai sus devine:

Datorita alegerii punctelor in mod random in timpul calcularii lui {$C{~I,B~}$}, fiecare punct din {$I$} are probabilitatea {$^1^/{~N~}$} de a fi ales. De asemenea, datorita faptului ca cercul de raza minima care cuprinde toate punctele din setul {$I$} este determinat de 2 sau 3 puncte, la fiecare apel al functiei exista maxim 3 puncte pentru care cercul {$C{~I - {P},B~}$} va trebui marit. Astfel probabilitatea ca {$P$} sa nu apartina cercului {$C{~I - {P},B~}$} este egala cu {$^3^/{~N~}$}. Inegalitatea devine:

* {$T(N) <= T(N - 1) + ^3^/{~N~}*O(N) + O(1)$}
ceea ce este echivalent cu

Astfel complexitatea devine {$O(N)$}. Se demonstreaza analog pentru {$|B|$} egal cu 0.

 
%{color:red}TODO: demonstrat de ce pentru orice set de puncte exista doar 3 care pot sa fie in afara cercului%
 

Exercitii: "SPOJ ALIENS":http://www.spoj.pl/problems/ALIENS/