# Tag Info

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