algorithm - how can i prove the master theorem for quicksort

Question

i have a question regarding the algorithm, quicksort. Can someone explain me how i get to the result (proof) 2T(n/2) + Θ(n) ? And what that result means : T(n-1) + Θ(n).

Thanks for all answers.

Answer 1

Master theorem states that,

For any ,

1. If for some constant , then .
2. If , then .
3. If , for some constant , and if for some constant and all sufficiently large , then

As for yours,
,

Here,
(2nd condition)
So the complexity will be:

For your second question, to understand this function , you need to understand divide and conquer method. In quick sort, for n items if you take the last value as pivot, the number of items will decrease by 1, which will reduce the number of items to (n-1), Now if you recursively call quick sort taking last value as pivot, each time one item will be reduced. Thus the complexity will be , which is not the case when you take middle value as pivot.