Show that $2^n$ not in O(1)

Question

I am currently stuck at a problem with the Big-Oh. The actual problem is this:

" Find the mistake in the following proof:

Proposition: $2^n$ = O(1)

Proof: Through induction. Proposition is correct for n = 0, because 1 = O(1). Let's propose that $2^{n-1}$ = O(1). We have to show that $2^n$ = O(1) but that is obvious because: $2^n = 2 * 2^{n-1} = O(2^{n-1}) = O(1)$. "

Ok, my problem now is that I wanted to first proof that $2^n$ is not in O(1) before checking the induction for mistakes. The Big-Oh always was a problem for me because I never understood it well but now I need it in this class. This is as far as I got:

$ \lim_{n \to\infty} \frac{2^n}{1} = \infty$

So now I got this but I don't know how to proceed or if this is actually the proof that it isn't in O(1).

Can anybody help me?

Thank you in advance!

Answer 1

The answer to your question so far: Yes, $\lim_{n\to\infty}\frac{2^n}{1} =\infty$ exactly proves that $2^n\ne O(1)$. this is how we would usually check if $f=O(g)$.

So, have you worked on finding the flaw in the proof?

EDIT: The problem with the proof is actually that induction can simply not be used in this situation (as Hagen von Eitzen's answer also says). Induction is used to prove that a property holds for any fixed natural number $n$. However, being Big-Oh of something is a property of the function $f(n)=2^n$ (this is also what John Hughes is talking about).

It doesn't make sense to ask: Is $(n\mapsto2^n) = O(1)$ for $n=1$? For $n=2$? For $n=3$? Etc. This is what induction does. Basically, we have shown that the constant functions $2^1, 2^2, 2^3, \ldots$ are all $O(1)$. But this says nothing about the behaviour of the function $2^n$.

Does it make sense?

Answer 2

Recall that $f\colon \Bbb N\to\Bbb R$ is $\in O(g)$ if $$ \exists c\colon \forall n\colon f(n)<c\cdot g(n)$$ (I deliberately left out that we should have "for almost all $n$" instead of "for all $n$"). However, statements provable by induction always have the form $\forall n\colon \ldots$. In other words, the induction "proof" at best can show something like $$\forall n\colon\exists c\colon f(n)<c\cdot g(n).$$ Order of quantifiers matters.

Answer 3

I'm going to say something radical here (which is a generalization of @Hagen's comment). Others may disagree.

1. Big-O can be regarded as a function that consumes (for the sake of computer science, which seems to be where you're coming from) functions from $\Bbb N$ to $\Bbb R^+$ and produces sets of such functions.

2. Because of this, the argument to big-O is a function, and should (at least initially) be written as a function. Since we know the domain and codomain, all you need is the "mapping" part. So when you want to talk about what folks call $O(1)$, you should instead write

$$ O(n \mapsto 1). $$ Equally good, and denoting exactly the same set, are $O(k \mapsto 1)$, $O(p \mapsto 1)$, and $O(j \mapsto 7)$, although you'll seldom see anything like that last one.

Those who insist that the $n$ in $O(n)$ is already a function should give an answer to these questions: (1) is $O(k)$ the same as $O(n)$? (2) is $n \mapsto n$ in $O(n)$? Is $n \mapsto n$ in $O(k)$? Is $n + k \mapsto n$ in $O(k)$? [If your answer to any one of these begins, "Well, you have to understand the context for any one of those questions to make sense...", then I claim you've got a rotten notation to introduce a concept to students.] Don't get me wrong: I'm quite happy to see mathematicians use $o(1)$ and $O(n)$, etc., because it's shorthand that we all know and understand. But that doesn't mean that it's the right way to introduce the concept to students!

Once you recognize that big-O notation is all about functions (rather than particular values), you can carefully read the definition, which might as well (at least for the CS context) be $$ f \in O(g) $$ if and only if there's a pair of positive numbers $(M, c)$ with the property that for all $n > M$, we have $f(n) \le c \cdot g(n)$. (Alternatively: such that $$ n > M \implies f(n) \le c \cdot g(n) $$ but frankly, that doesn't read as nicely from my point of view.)

With this in mind, try to replace every sentence in the supposed "proof" with the actual definition/meaning and see where you reach a point that's complete nonsense. It's pretty early.

Side note: the terminology that "$f$" is $O(g)$" (or worse still, the abomination $f = O(g)$) is another horrible usage, especially for beginners. What does "is" mean in that sentence? Is it like "$a$ is $4$"? Because in that case, $n$ is $O(n)$, and $2n$ is $O(n)$, so $n$ is $2n$, right?

Obviously not, but now you're relying not only on my understanding your sloppiness in notation, but also your sloppiness in language. "No, no," you say, "O(n) is just being used as an adjective here, like "blue" or "constant." How can you object to that?" Well... it's pretty easy. If every set can be treated as an adjective, I might as well say that $4$ is $\{1, 4, 5\}$. I mean, you know what I mean, right? Of course you do! And the unit 2-sphere is the set of all smooth surfaces. I can't imagine why anyone would object to that.

"No, no," you cry, "The problem was back when you defined $O(n)$. You shouldn't have defined it as a set -- you should have made it clear that it was an adjective, like "continuous" or "smooth"! That's where you went off the rails."

Fair enough. But if we're going to do that, then why are you using an "equals sign", which denotes actual equality, to replace the adjectival form of "is"? I don't say "My shirt equals blue," do I? And even without the equals sign, what on earth could it mean when you write "$O(1) \subset O(n)$"? How can one adjective be a subset of another?

---

You may think that this imagined discourse is fictional. It's not. It's me, arguing with one of my colleagues (who is, by the way, a good friend of mine. He's just wrong about this one thing, just as I am wrong about so many others).