# How to find the big O notation of $\log^b x$

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?

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.

• What's $T(x)$? Who said anything about time? It's best to avoid introducing extraneous details and say that a function is polylogarithmic if it is a polynomial in $\log x$ (i.e., has the form $\sum_{i=0}^k a_i\log^i x$). – David Richerby Nov 7 '13 at 9:30
• @DavidRicherby feel free to edit. – Realz Slaw Nov 7 '13 at 15:28

To answer any question about $O(-)$ notation, you need to check the definition, which is that, for functions $f$ and $g$, $f=O(g)$ if, and only if, there are constants $x_0$ and $k$ such that $|f(x)|\leq k|g(x)|$ for all $x\geq x_0$.

$O(-)$ is often treated as some fixed hierarchy of functions, "logarithms are $O$(polynomials), polynomials are $O$(exponentials)" and so on, leading students to believe that you can only write $O(g)$ for some very special or very nice functions $g$. This is quite simply not true: the definition allows you to write $O(g)$ for any function of one variable that you want to. For constant $b$, you can write $O(\log^b x)$. Heck, you can write $O\big(\sin\,(\cos\tfrac{1}{x^2})+3\big)$, if you want to, though you probably never will want that.

A good "rule of thumb" to use with asymptotic notation is: $O(n^n) > O(k^n) > O(n^k \log^l n) > O(n^k) > O(log^k n) > O(1)$

So if you have $n^3 + log^b n$, the $n^3$ term will dominate, giving you $O(n^3)$.