Tagged Questions
2
votes
1answer
98 views
Lower bound for matrix sorting?
Consider the problem of sorting a $n$ by $n$ matrix i.e. the rows and columns are in ascending order. I want to find the lower and upper bound of this problem.
I found that it is $O(n^2logn)$ by just ...
2
votes
1answer
61 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
0answers
41 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 = ...
8
votes
1answer
3k views
Quicksort Running Time
I am trying to refresh my knowledge (and hopefully learn more) about Algorithm Analysis. I took a course on this two years ago but I am trying to catch up on what I had learned back then.
The way I ...
