# Check Welzl's algorithm time complexity

From the wiki this is the algorithm and we know that final complexity is O(n) but how we reached to this , is my problem :

algorithm welzl is
input: Finite sets P and R of points in the plane |R| ≤ 3.
output: Minimal disk enclosing P with R on the boundary.

part 1: if P is empty or |R| = 3 then
return trivial(R)
part 2: choose p in P (randomly and uniformly)
part 3: D := welzl(P − {p}, R)
part 4: if p is in D then
return D

part 5: return welzl(P − {p}, R ∪ {p})


My try:
Easiest one, part 1 has O(1) time.
part 2 has O(1) time.
part 3 is something like T(n) = T(n-1).
part 4 is in O(1) time.
part 5 is something like T(n) = T(n-1) because we eliminate 1 point and increase R but we will work more with P so that would be the recursive equation.

If I writed correctly my analysis(and I'm sure it have incorrect parts) I don't know how to combine this 5 parts time complexity inorder to reach O(n).is the final equation like this?:$$T(n) = 2T(n-1)$$
but the final answer will be exponential .

Note that the expected running time analysis is $$O(n)$$. It is given in the original paper itself (Section 2).

Here, I am simply analyzing the worst-case time complexity of the algorithm. Note that Part $$3$$ and Part $$5$$ are not the same.

Let $$T(n,r)$$ denote the complexity of algorithm when $$|P| = n$$ and $$|R| = r$$. Then, Part $$3$$ corresponds to $$T(n-1,r)$$ and Part $$4$$ corresponds to $$T(n-1,r+1)$$.

\begin{align} T(n,r) &= T(n-1,r) + T(n-1,r+1) + O(1) \\ &= T(n-2,r) + T(n-2,r+1) + T(n-1,r+1) + O(1) \\ &= \dotsc \\ &\leq n \cdot T(n,r+1) + O(1) \quad \textrm{(since T(0,r) = O(1))}\\ &\leq n^2 \cdot T(n,r+2) + O(n) \\ &\leq n^3 \cdot T(n,r+3) + O(n^2) \\ ​ \end{align}

At the start of the algorithm, we have $$r = 0$$. Also, $$T(n,3) = O(1)$$ corresponding to Part $$1$$. Therefore, $$T(n,0) = O(n^3)$$ is the worst case time complexity of the algorithm.

• Thanks for thr analysis but you said that expected time complexity is O(n) and at the end of the answere we found that it is O(n^3) . Why? Dec 25 '21 at 19:08
• @program_craft It is a randomized algorithm. I did not prove the expected running time complexity of the algorithm. I simply proved the (deterministic) worst-case running time of the algorithm. Dec 26 '21 at 6:40
• I voted up your answer because that was nice for the worst case but I still waiting for calculating expected time for accepting the answer . If you can do that too that will be nice Dec 26 '21 at 10:01
• @program_craft. Thanks for being honest. How about you give it a try by yourself. If you get successful then write a new answer and let me know. Or if you get in trouble, update your question; I will help then. Dec 26 '21 at 10:52