I'm learning Big-O notation in school and my friend and I have a hard time understanding some parts of it and we don't agree on some answers in the exercises.

There are two cases on which we don't agree, and they are particularly easy ones.

The following example contains both cases:

We need to find the Big-O of $f(n) = 6n^{10} + 3^{3n-6}$.

We know we have to separate the function in two distinct parts, namely:

$$f_1(n) = 6n^{10},$$

$$f_2(n) = 3^{3n-6}$$

and the maximum of the two is going to give the Big-O of the equation.

While, from what I've read in the textbook, $f_1$ should give a Big-O of $n^{11}$, my friend thinks it should be $n^{10}$.

As for $f_2$, I think the Big-O should be $3^{n}$ while he thinks it should be $3^{3n}$.

I'm looking for an explanation to know how I should be getting the correct results, no matter what they are. There are some theorems in the textbook for other types of functions (log, factorial, etc.), but I have no idea how to get the results for the two I mentioned earlier in this post.

Both relations $f_1(n) = \mathrm O(n^{10})$ and $f_1(n) = \mathrm O(n^{11})$ are correct since Big-O is upper bound, not obligatory exact. However $\mathrm O(n^{10})$ gives you more tight bound.
Relation $f_2(n) = \mathrm O(3^{3n})$ is obviously correct, but $f_2 = \mathrm O(3^n)$ is not correct since for any $c$ there exist $N_c = 3 + \left\lfloor\frac{\log_3 c}2\right\rfloor + 1$ such that for all $n \ge N_c$ we have $3^{2n-6} > 3^{6 + (\log_3 c) - 6} = 3^{\log_3 c} = c$ and therefore $f_2(n) = 3^{3n - 6} > c 3^n$.
• I needed to show that $f_2(n) = 3^{3n-6} > c 3^n$ for any constant $c$ and big enough $n$. It is the same as $3^{2n-6} > c$. – Smylic Oct 15 '13 at 1:48