Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
This question already has an answer here:
I have two functions, $$ f = n^{1.6} $$ $$ g = n^{1.5} $$
I thought this is $ f=\theta(g) $, since $ f $ is asymptotically tight bound of $ g $, if $ n $ goes to infinity.
However, the answer is $ f = \omega(g) $.
Can anyone explain why it is $ f = \omega(g) $ ?
Thanks in advance!
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
$\frac{f(n)}{g(n)} = \frac{n^{1.6}}{n^{1.5}} = n^{0.1}$ is unbounded. Hence, for any $c > 0$ there is $n_0 \in \mathbb{N}$ such that $n^{0.1} > c$ for all $n > n_0$. As a result, for any $c > 0$, we have $n^{1.6} = n^{0.1} \cdot n^{1.5} > c n^{1.5}$ for all $n > n_0$.
Notice this does not really make use of $1.5$ and $1.6$ other than $1.6 > 1.5$. In fact, using the same method and the fact that $n^\varepsilon$ is unbounded for any $\varepsilon > 0$, you can prove the more general bound $n^a \in \omega(n^b)$ for any $a > b \ge 0$.
