All Questions
Tagged with sorting recurrence-relations
6
questions with no upvoted or accepted answers
2
votes
0
answers
650
views
Setting up a recurrence for Odd-Even Mergesort
Given the below algorithm
How would one go about setting up a recurrence for both that merging algorithm AND using this "new" merging algorithm in a traditional merge sort?
What I've tried
For the ...
2
votes
0
answers
454
views
Setting up and solving a recurrence relation
Assume we have two lists, $A$ and $B$; both are sorted lists each with $n$ elements (assume $n$ is a power of 2).
We want to recursively merge the odd-indexed elements from each list: merge $a_1, a_3,...
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}\...
1
vote
0
answers
52
views
Recurrence in exercise divides and conquers
I am new to this site, I hope to contribute.
For now i have the following problem of recurrences in a subject of discrete mathematics:
Consider the algorithm, called StoogeSort in honor of the ...
- 11
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
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