O(n^3) or O(n^2)?

[izard]

Those interview questions... I am not fond of computer science riddles, but some are.

I am reasoning about Welzel's algorithm complexity:
(to find a minimal bounding circle over set of points P, there is a recursive algorithm:
circle mbcr(P[n], R)
if |P| = 0 or |R| = 3
return get_circle(R)
if (P[0] in mbcr(P-P[0], R))
return mbcr(P-P[0], R)
return mbcr(P-P[0], R+P[0])

In a textbook, they say complexity is ϴ(n) for average case and O(n^2) in worst case..

I am getting different values. Lets assume worst case, when "if (P[0] in mbcr(P-P[0], R))" is always false.
mbcr(n, |R|=3) = O(1) - obviously.
mbcr(n, |R|=2) = O(n) - n * first recursion point, and each time it gets only once to second recursion point (which is mbcr(n, |R|=3) case).
mbcr(n, |R|=1) = O(n^2) - T(mbcr(n, |R|=1)) = O(n) + (n-1) * T(n-1, |R|=2)) = O(n + n^2) = O(n^2)
mbcr(n) = O(n^3) - T(mbcr(n)) = O(n) + (n-1) * (T(mbcr(n-1,|R|=1)) = O(n) + O(n^3) = O(n^3)

What am I missing?? Everything above seems very clear for me, can't stop thinking about this simple problem.

Comments

[sab123]

First, an obvious moment that they should cache the result of mbcr(P-P[0], R) to avoid calling it twice. If I remember right, calling it twice will make the run time exponential. It's exponential and not quadratic because adding an extra point would double the amount of computation.

Now let's consider the best case. What is the best case? It's when the last 3 points form the boundary of a circle where all the other points fit. In this case the run time will obviously be linear, just computing mbcr(P-P[0], R) on each step.

What is the worst case then? If each point doesn't fit into the circle formed by all the following points. So on each step it would first compute mbcr(P-P[0], R) and then mbcr(P-P[0], R+P[0]). So if the cost of both were linear, this also would be exponential and not quadratic. And I think they are. mbcr(P-P[0], R) is obviously at least linear. mbcr(P-P[0], R+P[0]) seems to be limited by R reaching the size of 3. But before it tries to grow R, it would still try to recurse down all the way in its nested call of mbcr(P-P[0], R) which is linear. Thus I think that this specific algorithm is exponential.

But maybe it can be converted to a quadratic one:

Start with 3 points. They obviously define a circle.
while there are more points {
Add the next point.
If it falls within the existing circle, this is the easy case.
Otherwise try every combination of (the new point, two of 3 previous boundary points). This step will be linear because it needs to check the resulting circle against every other point, and the number of attempts is always fixed to 3.
}

The part I'm not sure about is whether replacing 1 point in 3 would always be enough to form a new circle that includes everything but it's a reasonable guess.

[izard]

Wikipedia says it is O(n). I also thought first it is exponential O(2^n), but then I ran several simulations and found my code in O(n^3). Now debugging my code, spamsink in lj ran same code and found it sub-quadratic.