1
$\begingroup$

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!

|cite|improve this question
$\endgroup$
  • $\begingroup$ What do you mean by "$f$ is asymptotically tight bound of $g$"? Are you sure you have understood the definition of $\Theta$? $\endgroup$ – dkaeae Feb 23 at 21:34
  • $\begingroup$ @dkaeae I think so. The definition of $ theta $ is, $ 0 <= c_1 g(n) <= f(n) <= c_2 g(n) $ for $ 0<= c_1 <= c_2 $. I thought $ x^{0.1} $(their difference) really does not matter if $ x $ goes to infinity. That's why I am thinking it is $ theta $. $\endgroup$ – jayko03 Feb 23 at 21:44
  • 1
    $\begingroup$ That difference does matter. $x^\varepsilon$ is unbounded for any $\varepsilon > 0$. $\endgroup$ – dkaeae Feb 23 at 21:47
  • $\begingroup$ @dkaeae Okay. what if the difference is 0.000001 like very small number. Does it still matter? Just want to make sure. $\endgroup$ – jayko03 Feb 23 at 21:49
  • 1
    $\begingroup$ In mathematics, "very small" is a relative notion. $0.000001$ is gigantic compared to $10^{-100}$. It does not matter as long as it is strictly greater than zero. $\endgroup$ – dkaeae Feb 23 at 21:50
1
$\begingroup$

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

|cite|improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.