1
$\begingroup$

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 .
If I made any mistake can someone help me please?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Dec 25 '21 at 19:08
  • $\begingroup$ @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. $\endgroup$ Dec 26 '21 at 6:40
  • $\begingroup$ 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 $\endgroup$ Dec 26 '21 at 10:01
  • $\begingroup$ @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. $\endgroup$ Dec 26 '21 at 10:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.