All Questions
3
questions
-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
2
votes
1
answer
89
views
Flawed twofold induction on an inequation (but where?)
The following induction is flawed because the result admits a counter-example, but I can't find where is the flaw. Please advise. [Edit: As pointed out in the answer, the error was in the base case. ...
2
votes
0
answers
88
views
On bounding the average cost of top-down merge sort
Let $A_n$ be the average number of comparisons to sort $n$ keys by merging them in a top-down fashion (see any algorithm textbook). It can he shown that
$$
A_0 = A_1 = 0;\quad A_n = A_{\lfloor{n/2}\...