All Questions
Tagged with sorting recurrence-relations
14
questions
1
vote
1
answer
436
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
3
votes
1
answer
113
views
Generalized Catalan number satisfying recursive definition
Wondering if the numbers satisfying the following relationship have a name or known closed-form solution. They show up in enumerating possible configurations of swaps during the execution of a bubble ...
- 133
0
votes
2
answers
142
views
Concrete Mathematics: Simplification of quick sort recurrence in preparation of finding summation factor
In the analysis of the quicksort algorithm a recurrence is presented in 2.12. I feel I understand the simplification steps down to the point where we have
$$
nC_n - (n - 1)C_{n-1} = 2n + 2C_{n-1},\ \ \...
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
1
answer
231
views
Concrete Mathematics: Quicksort analysis
I'm trying to work my way through Concrete Mathematics (2nd Edition).
I'm struggling to understand the transition for the analysis of the quick sort algorithm from the recurrence to the harmonic ...
- 23
2
votes
0
answers
649
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
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
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
-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
2
votes
1
answer
89
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
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}\...