Algorithm Comparison with Theta-notation

Question

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,

Answer 1

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