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)$