Search code examples
algorithmmathquicksort

how can i prove the master theorem for quicksort

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.

Solution

  • Master theorem states that,

    For any main function,

    1. If 1st condition for some constant Epsilon > 0, then T(n).
    2. If 2nd condition, then formula.
    3. If 3rd condition, for some constant epsilon, and if function for some constant c < 1 and all sufficiently large n, then T(n)

    As for yours,
    function,
    a = 2, b = 2
    Here,
    Theta (2nd condition)
    So the complexity will be: complexity

    For your second question, to understand this function 2nd question, 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 2nd question, which is not the case when you take middle value as pivot.