0
$\begingroup$

I'm just trying to get my understanding of big O down. I know the concept and the basics but I'm a bit confused about what it means to be equal to big O of something.

For example, is $2^{2n} = O(2^{100n})$? From my understanding it is, since $2^{2n}$ is "faster" than $2^{100n}$, and so completes within the time $2^{100n}$. Is this correct? And if this is true, does it mean that $n$ could have any coefficient greater than $2$ (in this case) such that $2^{2n}$ is equal to $O(2^{mn})$, for all $m > 2$?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Hi IABP, please see our existing questions on this topic: cs.stackexchange.com/q/824/755 and cs.stackexchange.com/q/57/755. They provide a great deal of material: if you study them carefully, you should have all the tools needed to answer your question. In general, it's a good idea to do a search before asking (search both on this site, and on Google) -- we expect you to do some research before asking. It also helps to show what you've tried (e.g., how you've tried to answer the question), and to read the help center (see upper-right corner of the site). $\endgroup$
    – D.W. ♦
    Nov 18 '13 at 2:29
  • $\begingroup$ One small point: avoid using words like "faster" to describe functions. An algorithm that runs in time $O(2^{2n})$ is indeed faster than one running in time $O(2^{100n})$ but the notation $O(-)$ has nothing to do with speed: it can describe any function. Likewise, driving at 100mph is faster than driving at 50mph, that doesn't mean that 100 is faster than 50. For functions, it's particularly confusing to use this terminology, since it contradicts the usual usage which is that the function $2^{100n}$ grows faster than $2^{2n}$ -- the exact opposite of the relationship you're talking about! $\endgroup$
    – David Richerby
    Nov 18 '13 at 11:40
  • 2
    $\begingroup$ @DavidRicherby "An algorithm that runs in time $O(2^{2n})$ is indeed faster than one running in time $O(2^{100n})$" -- False. First of all, faster for which $n$? Depends on the constants. Secondly, $O$ yields only upper bounds which may be arbitrarily sloppy. You want to use $\Theta$. $\endgroup$
    – Raphael ♦
    Nov 18 '13 at 21:08
6
$\begingroup$

The equality symbol used in the Big-O notation is actually abuse of notation, at least this is the way I see it. It is used here for convenience, I guess. Actually, $O(f(n))$ is a set of functions $g(n)$ for which there exists $C$ and $n_0$ such that $Cf(n) \geq g(n) \geq 0, n \geq n_0$. Saying that $g(n) = O(f(n))$ you are actually saying $g(n) \in O(f(n))$.

More informally, $g(n)$ belongs to the set of those functions that can eventually be bounded from above by $f(n)$, up to some constant.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Abuse of notation is right... $\endgroup$
    – Nik Bougalis
    Nov 18 '13 at 5:21
  • $\begingroup$ The abuse of notation is so completely standard that it's not worth getting upset about. $\endgroup$
    – David Richerby
    Nov 18 '13 at 11:36
  • $\begingroup$ @DavidRicherby I strongly disagree. In teaching, it's almost always better to be clear about things; students should know what the mathematics behind the supposedly convenient notation are. The amount of questions we get which originate in mis-calibrated intuition by abuse of notation is a sad testament to that. Also, I have seen too many alleged experts doing horrible things with Landau notation to believe that nothing bad ever happens. (See also your own comment above.) $\endgroup$
    – Raphael ♦
    Nov 18 '13 at 21:11
  • $\begingroup$ @Raphael Yes, I messed up above; thanks for the correction (unfortunately, it won't let me edit my comment). However, that mistake had nothing to do with $f=O(g)$ vs $f\in O(g)$. $\endgroup$
    – David Richerby
    Nov 18 '13 at 22:35

Not the answer you're looking for? Browse other questions tagged or ask your own question.