All Questions
7
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
1
answer
89
views
Generating function of recursive algorithm with random subcalls
I was presented with the following algorithm. As input the algorithm gets an array of length $n \geq 0$. If $n \geq 2$ then for each $k \in \{1, 2, ..., n\}$ the algorithm calls itself recursively ...
- 15
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,...
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
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