All Questions
Tagged with sorting asymptotics
13
questions
1
vote
0
answers
124
views
Been trying to prove that $n! = \Omega(n^{100})$. I was approaching it with the solution below. I am not really sure my assumptions
We know that:
$$f(n) = n! = \Omega (g(n)$$
if
$$g(n) = O(f(n))$$
then,
$$f(n) \in O(g(n))$$
If
$$ f(n) \leq c \cdot g(n) \quad \textbf{for all $n\geq 1$}$$
then, assuming $n=1$ and $c=100^{100}$:
$$n^{...
- 21
1
vote
1
answer
86
views
Does one level of worst-case recursion in quicksort cost $\Theta(n^2)$ or $\Theta(n)$?
Page 180 (section 7.4.1) of CLRS 3rd edition says
a worst-case split at every level of recursion in quicksort produces a $\Theta(n^2)$ running time
It seems that $\Theta(n^2)$ should be $\Theta(n)$ ...
- 1,454
1
vote
2
answers
41
views
Searching/Sorting Algorithm
I just started studying algorithms and data structures and came across this problem:
Given $x \in \mathbb{N}$ and two integer Arrays $A_1$ and $A_2$ each of the length $n$. Write an algorithm in ...
- 105
3
votes
4
answers
2k
views
Merge sort seems to take the same number of comparisons for best and worst case.
I am trying to clear up my conceptions of merge sort. What I cannot understand how merge sort takes less number of comparisons during best case.
Let me explain, looking at the merge procedure given ...
- 1,025
0
votes
1
answer
33
views
Question regarding the $\mathcal{O}$ notation used on constant functions
I'm having difficulties to understand the following passage out of the CLRS book, when the Counting Sort algorithm is introduced:
Counting sort assumes that each of the elements is an integer in ...
- 4,212
1
vote
2
answers
8k
views
Comparison between $n\log n$ and $n^2$ sorting algorithms
Suppose we have two sorting algorithms which takes $O(n\log n)$ and $O(n^2)$ time. What can we say about it? Is it always better to choose $n\log n$ if the size $n$ is not given? Or can we say on an ...
- 647
0
votes
1
answer
32
views
How big the maximal decrease in consecutive elements of a sequence?
Consider a sequence $(s_1, ..., s_k)$, and we have it sorted in decreasing order $(\tilde{s}_1, ..., \tilde{s}_k)= (\sigma(s_1), ..., \sigma(s_k))$.
Define $k_{\max} = \max \left( \max_i \left( s_i ...
- 2,670
1
vote
1
answer
103
views
correcting an invalid binary heap in $\Theta (n)$
We are given a binary max (every node is larger than its children) heap with $n$ elements.
We now change $\frac{n}{4}$ of the elements at random. We don't know which ones and to which value. And so, ...
- 12.8k
-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
1k
views
Lower bound for matrix sorting?
Consider the problem of sorting a $n$ by $n$ matrix i.e. the rows and columns are in ascending order. I want to find the lower and upper bound of this problem.
I found that it is $O(n^2logn)$ by just ...
- 239
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}\...
14
votes
3
answers
36k
views
Quicksort Running Time
I am trying to refresh my knowledge (and hopefully learn more) about Algorithm Analysis. I took a course on this two years ago but I am trying to catch up on what I had learned back then.
The way I ...
- 171