New answers tagged

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)$$


0

If oh is little, it is not possible. Because of the definition of these two symbols. $f(n) = \Theta(g(n))$ means there is two constants $c_1, c_2 > 0$ and $n_0 \in \mathbb{N}$ such that $g(n) < c_1 f(n)$ and $f(n) < c_2 g(n)$ for $n > n_0$. Hence, it means $\lim_{n\to \infty} \frac{f(n)}{g(n)} = constant > 0 $. However, the definition of the ...


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 \...


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)$.


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 ...


0

You need to know what you are up against. I assume that you compare one of the "fast" algorithms against an efficient implementation of either naive matrix multiplication or Strassen's 1969 algorithm (it seems that Strassen created an algorithm in 1986 that formed the basic of Coppersmith-Winograd and others). While the number of multiplications and ...


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$-...


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 (...


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 ...


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 ...


0

Dividing a 128 bit number by a 64 bit number can be done in constant time. If N is a prime that doesn't fit into 128 bit then the algorithm won't finish in your life time :-) Dividing two n bit integers can be done in O (n log n) for large n. But assuming that you use brute force division that does use $O (n^2)$ operations for a division, then you should ...


0

It is $(\lfloor \sqrt{N} \rfloor-1) \cdot O(n^2) = O(\sqrt{N} \log^2 N) = O(2^{\frac{n}{2}} n^2)$ in the worst case: for each of the $O(\sqrt{N})$ choices of the dividend you perform a division of two numbers of at most $n$ bits. (When you factor $N$ you might repeat some of the divisions, but these can be safely ignored since there can be at most $n$ ...


Top 50 recent answers are included