Group Activity:

Some big-O practice!

Discuss each of the formulas below, and determine a big-$O$, big-$Ω$, and big-Θ that are true for it. For right now, just use your intuition.

• $f_1(n)=3n^2+5n+3logn+25$
• $f_2(n)=10^{15}n+log_2(\frac{3n}{2})$
• $f_3(n)=12n+5^n+6n^3$

Next:

• prove that $f_1(n)$ is indeed in the big-$O$ class that you chose for it, by finding values for $c$ and $n_0$ that make the definition true

big-O = O(n^2).

c = 10

n_0 = 3

• prove that $f_2(n)$ is indeed in the big-$\Theta$ class that you chose for it, by finding values for $c_1$ and $c_2$, and a value for $n_0$ that make the definition true

big-$\Theta$ = $\Theta$(n)

c1 = 10^15

n_0 = 2/3

c2=10^16

• prove that $f_3(n)$ is in the big-$\Omega$ class you chose for it, similarly

big-$\Omega$ = $\Omega$(n)

c = 0

n_0 = 0

• for at least one of the functions, use the limits approach to show the same thing

$3n^2/n^2 + 5n/n^2 + 3logn/ n^2 + 25/n^2$

3 + 0 + 0 + 0

Limit n→ Infinity = 3