All Questions
5
questions
1
vote
1
answer
437
views
Modified quicksort
Quicksort has an expected runtime of $\mathcal O(n\log n)$ when choosing a pivot uniformly at random. Now consider that before each iteration of quicksort, we sample $\log n$ elements of the array and ...
- 181
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
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,...
4
votes
1
answer
26k
views
Recurrence Relation - Merge Sort
We know the recurrence relation for normal merge sort. It is T(n) = 2T(n/2) + n. After solving it we can get T(n) = cnlogn. I ...
- 143