False Claim that 2n = O(1)

This text discusses the false claim that 2n = O(1) and the bogus proof that is often given for this claim. The mistake in the proof is that it assumes that 2n is bounded by a constant, but this is not true for all values of n.

Questions

• Why is the claim that 2n = O(1) false?
• What is the mistake in the bogus proof for 2n = O(1)?
• Describe two functions f and g that are incomparable under big Oh.

Answers

• The claim that 2n = O(1) is false because 2n grows exponentially, while O(1) grows at most linearly.
• The mistake in the bogus proof for 2n = O(1) is that it assumes that 2n is bounded by a constant. However, this is not true for all values of n. For example, 2100 is much larger than any constant.
• Two functions f and g that are incomparable under big Oh are f(n) = n and g(n) = n log n. f(n) is O(g(n)) because n log n grows faster than n. However, g(n) is not O(f(n)) because n does not grow as fast as n log n.