Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 0 down vote accepted

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

share|improve this answer
    
Thanks a ton for the quick answer, it is very helpful. I can't upvote because I don't have enough rep yet, though. As for the part: 3^(2n-6), can you just explain why it is now 2n instead of 3n like in the original equation? –  JPInglio Oct 15 '13 at 1:20
    
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
    
Oh I see, sorry for that question, I should have known it. Thanks! –  JPInglio Oct 15 '13 at 1:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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