The Stack Overflow podcast is back! Listen to an interview with our new CEO.
6

If the $O$-complexity given is true, then $f(x)\leq c_2n\log n$ will not always be true. So in this case, how is $\Theta$-complexity different from $O$-complexity? Yuval has covered the quicksort aspects of your question but you have a couple of fundamental misunderstandings about asymptotics. There is no such thing as "$\Theta$-complexity" or "$O$-...


4

The worst-case running time of quicksort is $\Theta(n^2)$, and therefore quicksort always runs in $O(n^2)$, and this bound is tight (that is, best possible). The average-case running time of quicksort is $\Theta(n\log n)$. The best-case running time of quicksort is also $\Theta(n\log n)$, and therefore quicksort always runs in time $\Omega(n\log n)$, and ...


2

So I actually found the answers I was looking for. The case $c \ge 0$ is already handled in the question above. For the case $c < 0$ we have: \begin{align} n_{1/2} &= \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} \\ &\le \frac{|b| + \sqrt{b^2 - 4ac}}{a} \\ &\le \frac{|b| + \sqrt{b^2} + \sqrt{-4ac}}{a} \\ &= \frac{2|b| + \sqrt{4a|c|}}{a} \\ &...


2

Yes. Using L'Hospital: $\lim_{n \rightarrow \infty} \frac{\ln^k (n)}{\sqrt n} = \lim \frac{k \ln^{k - 1} (n) \frac{1}{n}}{ \frac{1}{\sqrt n }} = \lim \frac{ k \sqrt n \ln^{k -1 } (n) }{ n } = \lim \frac{k \ln^k (n)}{\sqrt n} = \dots = \lim \frac{k \cdot (k -1) \cdot \dots \cdots 2 \ln (n) }{ \sqrt n} = \lim \frac{k! \frac{1}{n}}{\frac{1}{\sqrt n}} = \lim \...


2

There is a bit of confusion. The number of comparisons when using Quicksort to sort n elements isn't a function of n, it's a function of n and the unsorted array. Now if you ask for "the largest number of comparisons for any array of n elements", "the smallest number of comparisons for any array of n elements", or "the average number of comparisons over all ...


1

So, we have that $f(n) = O(n^c \log^k(n)) = O(n^0 \log^2(n))$; and since $log_b(a) = log_2(1) = 0 = c$, we are in the 2nd case of the Master's theorem (work to divide the problems is comparable to the work on subproblems (wiki)); thus, applying the theorem, we get $T(n) = \Theta(log^3(n))$. On the floor operation, I don't know what is the cleanest way of ...


1

$\sum_{i=1}^k 2^i=\Theta(2^k)$ and you have $k\approx\log n$, so the sum is $\Theta(2^{\log n})=\Theta(n)$.


1

CLRS is wrong. For example, the function $0n^2+0n+0$ is asymptotically nonnegative but doesn't belong to $\Theta(n^2)$. Changing "nonnegative" to "positive" doesn't help: you can consider $0n^2+0n+1$. Even requiring the function to be nonconstant doesn't help: consider $0n^2+1n+0$. Here is a statement which is correct: if $a > 0$ then $an^2+bn+c = \Theta(...


1

Number of swaps: The number of swaps in Bubble sort is exactly the number of inverted pairs, i.e. the number of pairs $(i,j):i < j\wedge s[i]>s[j]$. This number of pairs should be $(n/2-1)+(n/2-2) + ... + 1$ which is of the order of $n^2$. Number of comparisons: This is of the order of $n$ times the number of passes through the list, which is of the ...


1

Dividing both sides by $n$ then introducing $S(m):=\frac{T(2^n)}{2^n}$ yields: $$S(m)=S(m/2)+1+\frac{1}{m}$$ It follows that: $$1<S(m)-S(m/2)\leq 2$$ And further: $$\forall k, 1<S(m/2^k)-S(m/2^{k+1})\leq 2$$ Now summing for $k=1\dots \log(m)-1$ gives us: $$S(m)=\Theta(\log(m))$$ And so: $$T(n)=\Theta(n\cdot\log\log n)$$


1

All improvements since Strassen's original algorithm only achieve their exponent in the limit. That is, if they are stated as $O(n^c)$ algorithms, what they really show is that for every $\epsilon>0$ you can multiply two $n\times n$ matrices using at most $C_\epsilon n^{c-\epsilon}$ multiplications, where the constant $C_\epsilon$ blows up badly (...


1

Basically, when you see $f(x)=o(g(x))$, it indicates that $\lim_{x\rightarrow\infty}\frac{f(x)}{g(x)}=0$. If you plug them in, e.g., $\lim_{x\rightarrow\infty}\frac{n}{n\log\log n}=\lim_{x\rightarrow\infty}\frac{1}{\log\log n}=0$, you will see they satisfy it.


1

1 For the first case, you had the right idea, but just had some algebra mistakes. for i=1..n j=1 while j*j <= i: j = j + 1 Let $T(n)$ be the time complexity. $$T(n) = \sum_{i=1}^n\sum_{j=1}^\sqrt{i}1\leq \sum_{i=1}^n\sqrt{n}=\leq n^{3/2}$$ $$= O(n^{3/2})$$ 2 I'm assuming you meant the pseudocode below since it is more analogous to ...


Only top voted, non community-wiki answers of a minimum length are eligible