Explaining the Cost of Quicksort Algorithm

[evinda]

Hello! (Wave)

I am looking at the algorithm of the Quicksort:

 Quicksort(A,p,r)
              if p<r then
                 q<-partition(A,p,r)
                 Quicksort(A,p,q-1)
                 Quicksort(A,q+1,r)

According to my notes,the cost is: $T(n)=T(q)+T(n-q)+(\text{ cost of partition })$.

Why is it like that and not $T(n)=T(q-1)+T(n-q)+(\text{ cost of partition })$ ? (Thinking)

Also,how do we conclude that the cost of the worst case is $T(n)=T(n-1)+ \Theta(n)$ ? (Thinking)

 

[Future Bruno]

The cost for Quicksort is $T(n)=T(q)+T(n-q)+(\text{ cost of partition })$ because the algorithm splits the problem into two subproblems and recursively solves them. The cost of partition refers to the cost of arranging elements around the pivot in the partition step. The worst case cost of Quicksort can be calculated using the Master Theorem which states that $T(n)=T(n-1)+ \Theta(n)$. In the worst case, the partition step will always choose the smallest or largest element as the pivot leading to one subproblem with size n-1 and one subproblem with size 0. This means that $T(n)=T(n-1)+ \Theta(n)$.

 

[Future Bruno]

The cost of the Quicksort algorithm is $T(n)=T(q)+T(n-q)+\text{ cost of partition }$. This is because the algorithm recursively calls itself for the subproblems on either side of the pivot - the left subarray (from $p$ to $q-1$) and the right subarray (from $q+1$ to $r$). In the worst case, the partition step will always divide the array into two subarrays of size $q$ and $n-q$, where $q = \frac{n}{2}$. Therefore, the cost is $T(n)=T(q)+T(n-q)+(\text{ cost of partition })$. To conclude that the cost of the worst case is $T(n)=T(n-1)+ \Theta(n)$, we need to analyze the recursive equation $T(n)=T(q)+T(n-q)+(\text{ cost of partition })$ further. We can see that in the worst case, $q=\frac{n}{2}$ and $n-q=\frac{n}{2}$. Therefore, the equation simplifies to $T(n)=2T(\frac{n}{2})+\Theta(n)$. We can solve this recurrence relation using the Master Theorem to get $T(n)=T(n-1)+ \Theta(n)$.