1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ 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$). $\endgroup$ – David Richerby Nov 7 '13 at 9:30
  • $\begingroup$ @DavidRicherby feel free to edit. $\endgroup$ – Realz Slaw Nov 7 '13 at 15:28
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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)$.

| cite | improve this answer | |
$\endgroup$

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.