2.1.7

Chad Birger 25 Jan 2009 20:09

a) $f(n) = \frac{n}{100000000} + 999999999$.

$f(n) = O(n)$

b) $f(n) = \log (n^2 + 1)$.

$f(n) = O(\log(n))$

c) $f(n) = \sqrt{n^2+1}$

$f(n) = O(n)$

d) $f(n) = \left(n^2+1\right)\left(n\log n + 1\right)$

$f(n) = O\left(n^3 \log n\right)$

e) $f(n) = 10^{1000}$

$f(n) = O(c)$ where $c$ is a constant

f) $f(n) = \frac{n+3}{n+1}$

$f(n) = O(3)$

g) $f(n) = \frac{n^3 + 1}{n+1}$

$f(n) = O(n^2)$

h) $f(n) = 2^{3 \log n} + n^3 + 4$

$f(n) = O(n^3)$

i) $f(n) = \frac{n!}{9999999} + 999999 \dot 2^n$

$f(n) = O(n!)$

j) $f(n) = \log_{10} 2^n + 10^{10} n^2$

$f(n) = O(2^n)$