Check Welzl's algorithm time complexity

Question

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?

Answer 1

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.