1
$\begingroup$

Is $n^3$ an asymtotically tight bound of $(n^{2.99}).(\log_2n)$? If so then how?

$\endgroup$
  • $\begingroup$ We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. $\endgroup$ – Raphael Oct 10 '18 at 6:12
2
$\begingroup$

No. $n^{2.999}\log_2n$ is tighter, for example.

$\endgroup$
1
$\begingroup$

$g(n)$ is an asymptotically tight bound of $f(n)$ if $f(n) = O(g(n))$, but $f(n) ≠ o(g(n))$. In this case, $n^{2.99} \log n = o (n^3)$. For very large n, $n^{0.01}$ grows faster than $\log n$.

$\endgroup$
  • $\begingroup$ I am afraid your definition of "an asymptotically tight bound" is not (equivalent to) the most common one. I would say "g(n) is an asymptotically tight bound of f(n) if and only if $f(n) = \Theta(g(n))$. $\endgroup$ – Apass.Jack Oct 10 '18 at 4:08
  • $\begingroup$ @Apass.Jack That is almost the same. Yuval's definition admits some funky $f$. $\endgroup$ – Raphael Oct 10 '18 at 6:13
  • $\begingroup$ @Raphael, yes, I agree these two definitions are almost the same. However, you know they are NOT the same. I just wanted to point out that it is better to simply say, "$g(n)$ is an asymptotically tight bound of $f(n)$ implies $f(n) = O(g(n))$, but $f(n) ≠ o(g(n))$". Where is Yuval's definition? $\endgroup$ – Apass.Jack Oct 10 '18 at 7:06
  • $\begingroup$ Right. think Yuval meant "tight upper bound". $\endgroup$ – Raphael Oct 10 '18 at 8:38
  • $\begingroup$ @Raphael, sorry if I am dense, but where is Yuval's definition? Do you mean that because @"Yuval Filmus" had edited this answer by gnasher729 without changing that definition, you guessed that Yuval meant "tight upper bound"? $\endgroup$ – Apass.Jack Oct 10 '18 at 13:17

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