All Questions
3
questions
1
vote
1
answer
437
views
Modified quicksort
Quicksort has an expected runtime of $\mathcal O(n\log n)$ when choosing a pivot uniformly at random. Now consider that before each iteration of quicksort, we sample $\log n$ elements of the array and ...
- 181
0
votes
2
answers
142
views
Concrete Mathematics: Simplification of quick sort recurrence in preparation of finding summation factor
In the analysis of the quicksort algorithm a recurrence is presented in 2.12. I feel I understand the simplification steps down to the point where we have
$$
nC_n - (n - 1)C_{n-1} = 2n + 2C_{n-1},\ \ \...
-1
votes
2
answers
1k
views
Need help analyzing a merge sort
Im working on trying to understand merge sorts better and had a professor give me this to try to help. It is finals week and I have been trying to walk through this problem but have been having ...
- 9