Pentru {$|B|$} egal cu 2, complexitatea este evident {$O(N)$}, deoarece calcularea cercului de raza minima pentru setul {$B + {P}$} se rezolva in {$O(1)$}.

Pentru {$|B|$} egal cu 1, notam cu {$T(N)$} numarul de operatii folosite pentru a calcula {$C{~S,B~}$}, unde {$|S|$} este egal cu {$N$}. Atunci {$T(N)$} respecta relatia:

Pentru {$|B|$} egal cu 1, notam cu {$T(N)$} numarul mediu de operatii folosite pentru a calcula {$C{~S,B~}$}, unde {$|S|$} este egal cu {$N$}.

* {$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$}.

Din setul {$I$} vom scoate un element la fiecare apelare a functiei MINCIRCLE, deci pentru a calcula numarul mediu de operatii pentru {$N$} elemente, adunam numarul mediu de operatii pentru {$N - 1$} elemente ({$T(N - 1)$}).
Fiecare punct din {$I$} are probabilitatea {$^1^/{~N~}$} de a fi ales in cadrul functiei. Din aceasta cauza, functia MINCIRCLE{$(I - {P}, B ∪ {P})$} va fi apelata cu o probabilitate egala cu (numarul de puncte {$P$} care nu apartin cercului {$C{~I - {P},B~}$}) / {$N$}. De asemenea, fiecare apel al acestei functii are complexitatea {$O(N)$}, dupa cum am demonstrat mai sus pentru {$|B|$} egal cu 2.

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:

Astfel {$T(N)$} respecta relatia:
 
* {$T(N) <= T(N - 1) + Probabilitatea( P nu apartine C{~I - {P},B~} ) * O(N) + O(1)$}
 
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
* {$T(N) <= T(N - 1) + O(1)$}

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

Astfel complexitatea devine {$O(N)$}. Demonstratia pentru {$|B|$} egal cu 0 se face in mod asemanator.
 
 
Ca o ultima precizare, exista si un algoritm de complexitate {$O(N log N)$} pentru aceasta problema, ce foloseste diagrame voronoi.

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