# Algorithm notation between two functions [duplicate]

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

## marked as duplicate by David Richerby, Evil, xskxzr, Yuval Filmus algorithms StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Feb 24 at 15:01

• What do you mean by "$f$ is asymptotically tight bound of $g$"? Are you sure you have understood the definition of $\Theta$? – dkaeae Feb 23 at 21:34
• @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$. – jayko03 Feb 23 at 21:44
• That difference does matter. $x^\varepsilon$ is unbounded for any $\varepsilon > 0$. – dkaeae Feb 23 at 21:47
• 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. – dkaeae Feb 23 at 21:50
$$\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$$.