2.15

(a) [math]n^2[/math]: doubling ⇒ ×4; adding 1 ⇒ ×[math]1+\dfrac{2}{n}+\dfrac{1}{n^{2}}[/math] (≈1)
(b) [math]n^{3}[/math]: doubling ⇒ ×8; adding 1 ⇒ ×[math]1+\dfrac{3}{n}+\dfrac{3}{n^{2}}+\dfrac{1}{n^{3}}[/math] (≈1)
(c) [math]100n^{2}[/math]: doubling ⇒ ×4; adding 1 ⇒ ×[math]1+\dfrac{2}{n}+\dfrac{1}{n^{2}}[/math] (constant 100 cancels)
(d) [math]n\log n[/math]: doubling ⇒ ×[math]2\!\left(1+\dfrac{\log 2}{\log n}\right)[/math] (→2 as n→∞); adding 1 ⇒ ×[math]\dfrac{(n+1)\log(n+1)}{n\log n}\approx 1+\dfrac{1}{n}+\dfrac{1}{n\log n}[/math]
(e) [math]2^{n}[/math]: doubling ⇒ ×[math]2^{\,n}[/math] (explodes exponentially); adding 1 ⇒ ×2

Back to Chapter 2