Massachusetts Institute of Technology Handout 29 6.042J/18.062J: Mathematics for Computer Science October 20, 2000 Professors Nancy Lynch and Srinivas Devadas

Mini-Quiz 6

1. Write your name:

2. (modified from Rosen, Section 1.8, Problem 13) Show that 2^{n} is O(4^{n}) but that 4^{n} is not O(2^{n}).

Solution: Since 2^{n} < 4^{n} for all n > 0, it follows that 2^{n} is O(4^{n}). However, if 4^{n} were O(2^{n}), then for some constant, C, 4^{n} ⩽ C.2^{n} for all sufficiently large n. This says that C ⩾ (4/2)^{n} for all sufficiently large n, which is impossible. Hence 4^{n} is not O(2^{n}).