0
$\begingroup$

We consider two algorithms, Algo1 and Algo2, that solve the same problem. For any input of size n, Algo1 takes time $T_1(n)$ and Algo2 takes time $T_2(n)$.

Prove or disprove each of the following statements.

To prove a statement, you should provide a formal proof that is based on the definitions of the order notations. To disprove a statement, provide a counter example and explain it.

Suppose that $T_1(n)$ ∈ $\theta(n^2)$ and $T_2(n)$ ∈ $\theta(n^3)$.

Does it imply that there exists $n_0$ such that for $n$ ≥ $n_0$, Algo1 runs faster than Algo2 on inputs of size $n$?

By definition of $\theta$-notation,$\\$

If $T_1(n)$ ∈ $\theta(n^2)$, then $c_1 n^2 \leq T_1(n) \leq c_2 n^2$ for all $n \geq n_1$for $c_1, c_2, n_1 > 0$.

If $T_2(n)$ ∈ $\theta(n^3)$, then $d_1 n^3 \leq T_2(n) \leq d_2 n^3$ for all $n \geq n_2$ for $d_1, d_2, n_2 > 0 $.

We choose $n_0 = max(n_1, n_2)$

Then, $\\$ $\frac{c_1 n^2}{d_1 n^3} \leq \frac{T_1(n)}{T_2(n)} \leq \frac{c_2 n^2}{d_2 n^3} \text{ for all } n \geq n_0$

$\lim_{n \rightarrow \infty} \frac{c_1 n^2}{d_1 n^3} = 0$ and $\lim_{n \rightarrow \infty} \frac{c_2 n^2}{d_2 n^3} = 0$

Hence, by Squeeze Theorem, $\lim_{n \rightarrow \infty} \frac{T_1(n)}{T_2(n)} = 0$. Therefore, Algo1 runs faster than Algo2 for $n >= n_0$

This is my solution, and I am wondering if this is right way to solve this question.

Any help is appreciated, thank you,

$\endgroup$
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. May 14 '18 at 0:52
  • $\begingroup$ I understand. Let me think how to fix the question. $\endgroup$ – user87320 May 14 '18 at 0:59
0
$\begingroup$

If $T_1(n) = \Theta(n^2)$ and $T_2 = \Theta(n^3)$, then since $n^2 = o(n^3)$, it follows that $T_1(n) = o(T_2(n))$. In particular, $T_1(n) < T_2(n)$ for large enough $n$. In fact, for every $C>1$, $T_1(n) < CT_2(n)$ for large enough $n$ (how large depends on $C$).

$\endgroup$
  • $\begingroup$ Hello professor, thank you for answering my question. So the conclusion is "since T1(n) < T2(n) for large n, there is no n0 such that n >= n0, Algo1 runs faster than Algo2". Is this correct ? $\endgroup$ – user87320 May 14 '18 at 13:30
  • $\begingroup$ Also is it okay to substitute = sign with ∈ sign ? $\endgroup$ – user87320 May 14 '18 at 13:31
  • $\begingroup$ I am wondering if my approach to solution is reasonable? $\endgroup$ – user87320 May 14 '18 at 15:01
  • $\begingroup$ Our approaches are identical. I just skip many steps. Regarding $=$ vs $\in$, the only place where I have seen $\in$ used is Computer Science. $\endgroup$ – Yuval Filmus May 14 '18 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy