0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.