2

The mistake and correction $$T(n)= 2T(n/2) + \theta(n^2)$$ As you intended, $T(n)$ is the worst time of mergesorting $n$ strings of length $n$. Then, $T(n/2)$ on the RHS means the worst time of mergesorting $n/2$ strings of length $n/2$. So during the mergesort, the length of strings shrinks from $n$ to $n/2$! What should have been done is using a ...


2

The fact that your algorithm is in Java or the source itself are not really relevant. That said, your algorithm requires time $\Theta(n \cdot k)$, where $n$ is the length of the input sequence, and $k$ is the length of the desired subsequence. This can be as bad as $\Theta(n^2)$, when $k=\Theta(n)$. You can improve the time complexity of your algorithm to $...


1

Your formulation of $f(n) \neq o(g(n))$ is wrong. Recall that $f(n) = o(g(n))$ if for all $c > 0$ there exists $n_0$ such that for all $n \geq n_0$, we have $f(n) \leq cg(n)$. The negation of this is: there exists $c > 0$ such that for all $n_0$ there exists $n \geq n_0$ such that $f(n) > cg(n)$. Take $c = 1$. Given $n_0$, let $n = \max(n_0,10^{...


1

One possibility is to merely apply the definition. That is, we see that if $\lim_{n \to \infty} f(n) / g(n) = 0$, then $f(n) = o(g(n))$. Computing this, we have that $$\lim_{n \to \infty} f(n) / g(n) = \lim_{n \to \infty} n^n/10^{10n} = \infty \neq 0.$$ We conclude that $f(n) = o(g(n))$ does not hold.


1

It is possible. Example $g_A(n)=1$, $g_B(n)=2$, and $f(n)=1$. It is also necessary, since $g_B(n) = 2 g_A(n) \in\Omega(f(n))$. To see that $ 2 g_A(n) \in\Omega(f(n))$ you can use the definition of $\Omega(\cdot)$. From $g_A(n) = \Omega(f(n))$ you know that here is some $n_0$ and some $c>0$ such that, $\forall n \ge n_0$, $g_A(n) \ge c f(n)$. This ...


1

Three for loops gets you to n^3. EDIT: for (int i=0; i < n; i++) // first n ..etc.. for (int j=0; j < n; j++) // second n ...etc... Outer two are n, that makes n^2 so far. Next look at inner loop: for (int k=0; k <= j; k++) // third n Innermost counts as another n for big O purposes even if running k to j instead of k to n. You're still on the ...


1

First of all notice that your first aggregate analysis should read $\sum_{i=1}^{\log n} 2^i = 2^{\log n + 1} - 2 < 2n$. (What you have written makes no sense since $\sum_{i=1}^\infty \frac{1}{2^i} \le 1$, which would mean that the aggregate complexity is upper bounded by a constant regardless of the number of operations). Then in your last analysis you ...


1

As each time $n$ is divided by $2$ and $2$ multiplied by 2, it should be: $$ T(n) = 2T(\frac{n}{2}) + 2^n $$ Now, if you expand it: $$ T(n) = 2(T(\frac{n}{2^2}) + 2^{\frac{n}{2}}) + 2^n = 2T(\frac{n}{2^2}) + 2 \times 2^{\frac{n}{2}} + 2^n $$ How can we guess $T(\frac{n}{2})$? Because $i$ is changing from $0$ to $\log{n}$. If we suppose $T(0)$, when $i = 0$,...


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