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 Oleft(log^b xright)$ or $mathcal Oleft(left(log xright)^bright)$ 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 Oleft(log^b xright)$ is called polylogarithmic time. In this case, $mathcal Oleft(x^3right)$ grows faster than $mathcal Oleft(log^b xright)$. 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
