All Questions
3
questions
1
vote
1
answer
64
views
Proof that mergesort uses $\sum_{1\le k < N}(\lfloor\lg k\rfloor+2)$ compares to sort $N$ elements
In the book "An introduction to the Analysis of Algorithms" by R. Sedgewick and P. Flajolet, There is this exercise
Exercise 1.4 Develop a recurrence describing the quantity $C_{N+1} − C_{N}...
4
votes
1
answer
219
views
Proof of Mergesort $N$ elements with $N \log N + O(N)$ comparisons
In the book "An introduction to the Analysis of Algorithms", written by Robert Sedgewick and Philippe Flajolet during the proof of the
Theorem 1.1: (Mergesort) To sort an array of N ...
- 43
0
votes
1
answer
607
views
Which one gives better constant factors between heap sort and quick sort?
Heap Sort has complexity $\mathcal{O}(n\lg(n))$ and Quick Sort with some tuning (choosing the pivot in a random order) on average also sorts in $\mathcal{O}(n\lg(n))$ and both of these are tight upper ...
- 2,349