# How do I find “Big Oh,” “Big Omega,” and “Big Theta”?

I need help studying for an exam. How do I find "Big Oh," "Big Omega," and "Big Theta"? How do I combine this with Induction?

• Prove that $f(x)$ is $O(x^n)$, where $$f(x) = a_n x^n + a_{n-1} x^{n-1} + a_{n-2} x^{n-2} + \cdots + a_2 x^2 + a_1 x + a_0$$
• Find "Big O": (Usually log in Computer Science is assumed to be base 2)

• $(2n+\log(n!)+3)(n^2+3\log n)(2^n+2)$
• $(3n+1)\log(n^5+7)+n!\log(n+\log n)$
• For each function, circle the sets that $f(n)$, $g(n)$ and $h(n)$ belong to:

1. $f(n) = n\log(n!) + 100$: $O(g(n))$, $\Theta(g(n))$, $\Omega(g(n))$
2. $g(n) = (n \log n)^2 + n^2$:
1. $O(n^3)$, $\Theta(n^3)$, $\Omega(n^3)$
2. $O(n^2)$, $\Theta(n^2)$, $\Omega(n^2)$
3. $O(n \log n)$, $\Theta(n \log n)$, $\Omega(n \log n)$
3. $h(n) = n(1000 + 2^n) + n!$:
1. $O(2^n)$, $\Theta(2^n)$, $\Omega(2^n)$
2. $O(n!)$, $\Theta(n!)$, $\Omega(n!)$
3. $O(n^n)$, $\Theta(n^n)$, $\Omega(n^n)$
-

For the first part, since $x^k \leq x^n$ for $k \leq n$ (whenever $x \geq 1$), the polynomial is at most $$(|a_n| + \cdots + |a_0|)x^n.$$

For the second part, the following facts are useful:

1. $\log n! = O(n\log n)$.
2. If $g(n) = o(f(n))$ then $f(n) + g(n) = O(f(n))$. For example, $2^n + 2 = O(2^n)$. The notation $g(n) = o(f(n))$ means that $\lim_{n\rightarrow\infty} \frac{g(n)}{f(n)} = 0$, i.e. $g$ grows much slower than $f$.
3. If $f_1(n) = O(g_1(n))$ and $f_2(n)) = O(g_2(n))$ then $f_1(n)f_2(n) = O(g_1(n)g_2(n))$.

For the third part, the following facts are useful:

1. $n! = \Theta(\sqrt{n}(n/e)^n)$ (Stirling's approximation).
2. $\log n = O(n^{\epsilon})$ for every $\epsilon > 0$.
-