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

Apr. 19th, 2017 08:08 pm**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.

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.