0
$\begingroup$

Assume that $c > 0$ is a constant and that $n$ is a positive variable. Then why is $n^{lg (c)} = O(c^{lg (n)})$? Furthermore, can you explain why $n^{lg (c)}$ is not $o(c^{lg (n)})$, that is $n^{lg (c)} \neq o(c^{lg (n)})$?

$\endgroup$
0
$\begingroup$

Taking the lg of both gives $\operatorname{lg}(c)\operatorname{lg}(n)$ so they are actually equal. Hence the provided asymptotics follow from $f\in\mathcal O(f)$ but $f\notin o(f)$.

$\endgroup$
  • $\begingroup$ I know that I have already accepted. But I wanted to say thank you. It really means a lot :) $\endgroup$ – over so Mar 26 at 11:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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