[Solved]: How to find the big O notation of $\log^b x$

Problem Detail: 

How would you determine big O notation for $\log^b x$? I don't think you can simply say $O(\log^b x)$, can you?

If you can, then here is a better question: $x^3 + \log^b x$. How would you know if it's $O(x^3)$ or something else depending on the $b$ value?

Asked By : Dan Webster

Answered By : Realz Slaw

How would you determine big o notation for this? I don't think you can simply do O(log(x)^b) can you?

$\mathcal O\left(\log^b x\right)$ or $\mathcal O\left(\left(\log x\right)^b\right)$ is correct.

x^3 + log(x)^b

Assuming $b$ is a constant. You always take the fastest growing term in a polynomial. $T(x)=\mathcal O\left(\log^b x\right)$ is called polylogarithmic time. In this case, $\mathcal O\left(x^3\right)$ grows faster than $\mathcal O\left(\log^b x\right)$.

You can see a list of different complexities (sorted from lowest to highest) here.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16781