CS2040s: Tutorial 2

c)/d)
1. Select pivot
2. Partition
3. Get index of pivot in new partition (i)
4. If smaller k, loop to left, else right
5. Partition again and repeat
6. Stop when i = k

This is O(n) in average
Is a summation = n + n/2 + n/4 + ... n/2^k
Because we are only doing one side each time

But O(n^2) in worst case
If we choose wrong pivot


e)
1. Select pivot
2. Partition
3. Get index of pivot in new partition (i)
4. If smaller than k, go to the right else left
6. Partition again until i = k

Is the same as d)/c)

It matters, time complexity, n + klogk