All Questions
2
questions
1
vote
0
answers
241
views
How to state a recurrence that expresses the worst case for good pivots?
The Problem
Consider the randomized quicksort algorithm which has expected worst case running time of $\theta(nlogn)$ . With probability $\frac12$ the pivot selected will be between $\frac{n}{4}$ and $...
- 1,884
1
vote
1
answer
87
views
Why is Mergesort $O(n)$ rather than $O(n\log{n})$?
Assume we want a divide-and-conquer algorithm that finds the max and min of a set $S$ with $n = 2^k$ elements, e.g. mergesort. The recurrence for time complexity is
$T(n)=2*T(n/2) +2$, for $n>2$, ...
- 83