0
$\begingroup$

I'm trying to figure out if:

  1. $\log^2n = O(n)$ and
  2. $ n = O(\log^2n)$

are true or if one or both are false.

So far I've concluded that both are false because if $n = 8$ for the first one, then $\log^2 8 = O(8)$ which is false since it simplifies to $9 = O(8)$ which does not belong to $O(n)$.

For the second one, I believe it to be false as well because if $n = 1024$ or (some other big number), you get $1024 = O(\log^2 1024)$ which simplifies to $1024 = O(100)$. And 1024 does not belong to $O(100)$.

Am I right or is one of these true? Thanks.

$\endgroup$
  • 1
    $\begingroup$ "$log^2 8 = O(8)$ which is false since it simplifies to $9 = O(8)$ which does not belong to $O(n)$." I'm sorry but that just doesn't make sense. $O$ is about asymptotic behaviour. As soon as you plug in a specific value of $n$, it stops making sense. In particular, for any positive constants $c$ and $d$, the statement $c=O(d)$ is true because there is a constant $k$ such that $c\le kd$ (take $k=c/d$). So, for example, the statement $e^x=O(x)$ is false but, if you pick any value for $x$, e.g., $x=3874$, the statement $e^{3874}=O(3874)$ is true. $\endgroup$ – David Richerby Nov 13 '15 at 20:38
  • 1
    $\begingroup$ See our reference question for how to do these things. Step one is, of course, to understand the definition of $O$. $\endgroup$ – Raphael Nov 13 '15 at 22:06
6
$\begingroup$

You're right about the second one, but your reasoning for both is sketchy. The definition of $f(n)=O(g(n))$ is that there exist constants $c,N$ both greater than zero such that $f(n)\le c\cdot g(n)$ for all $n\ge N$.

Trying a single value for $n$ won't generally give anything in the way of an answer. Consider, though, the intuition we get from trying $n=4, 8, 16, 32, \dotsc$: $$\begin{array}{lcccc} n: & 4 & 8 & 16 & 32 & 64 & 128\\ \log^2 n: & 4 & 9 & 16 & 25 & 36 & 49 \end{array}$$

It seems to be the case that $n$ grows much faster than $\log^2n$. In fact, for this example we have that at least for powers of 2, $\log^2(n)=\log^2(2^k)=k^2\le 1\cdot2^k=1\cdot n$ for all $n \ge 16$, so we might suspect that $\log^2n=O(n)$, which is indeed the case, as it happens.

What is most helpful is to get an intuition of the big-O relationship between frequently-used functions. Here are some examples (all of which should be proved, but that'll be up to you do do or look up). Assuming everything in sight is positive, then:

  1. $\log n = O(n^k)$ for any $k>0$. (polynomials beat logs, eventually)
  2. If $a \le b$, then $n^a=O(n^b)$. (polynomials behave as expected, by degree)
  3. If $a>1$, then $n^k=O(a^n)$. (exponentials beat polynomials)

and so on. The point here is that it's far better to develop your intuition and only use the definition of big-O when faced with a problem where intuition doesn't give you any help. That's what the experts do.

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