Time complexity of Quick Sort when pivot (split list into 90%:10%) (always smallest element for even depth)

Question

What is the time complexity of quicksort in the following 2 cases:

1. Pivot always split the list into 9:1 ratio
2. Pivot is always the smallest element(worst case) for even depth and the middle element(best case) for odd depth.

For 1, I guess we have the recurrence equation:

F(N) = F(N/10) + F(9N/10) + N

For 2,

F(N) = F(N-1) + N if even
F(N) = 2*F(N/2) + N if odd

Am I correct with these equations and how do I solve both of these recurrence equations?

Answer 1

Your formula is right, and both cases will give you a O(nlogn) complexity.

first proof:

if you write the recursion tree for the first case, you will see that from each node, you will branch to one node that is 1/10 the current problem size and to the other node that is equal to 9/10 of the current problem size.

it is intuitive that the left branch will reach the base case first (since we are using a smaller portion of the problem in this branch) and so the bigger complexity will be in the right branch.

everytime you go right, you will be solving a smaller problem that is 9/10 the size of the problem above it (its parent). So the question is, what is the depth of such a tree (how many times can I divide my problem by a factor of 10/9)

it is not hard to see that the answer is:

log(10/9) N

at each level of the tree we have to go through N values (which is the whole array or vector), therefore the time complexity is:

N * log(10/9) N = N * (log(2) N / log(10/9)

but log(10/9) is just a small constant, therefore the time complexity is:

N * log(2) N

second proof

it is very similiar to the other one, in this case the recursion tree depth will be twice larger than the perfect quicksort case (which is when we always get the middle value as a pivot)

to see this just imagine that half of the time we are going to hit the even condition, which will make us divide the array perfectly if such a condition happens half of the times, it means we will divide the array 2 times more than we would in a perfect world (pivot will always divide the array in half).

2 * N * log(2) N = N * (log(2) N

reference: https://www.khanacademy.org/computing/computer-science/algorithms/quick-sort/a/analysis-of-quicksort