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.

How can i prove this asymptotic equation?

$$2n^n + 2n^{n+1} = 2n^n + \Theta(2^n) $$

The theorem says: $$ \Theta(g(n)) = \{f(n): \exists c_1, c_2, n_0 > 0\,\, c_1g(n) \le f(n) \le c_2g(n), \,\,n \ge n_0\} $$ - $\Theta(\cdot)$ is used to asymptotically tight bound a function.

So i can simplify the equation like that:

$$2n^{n+1} = \Theta(2^n)$$

and we need to find

$$ c_1 \cdot 2^n \le 2n^{n+1} \le c_2\cdot 2^n, \quad n \ge n_0 $$


share|improve this question
3  
Is there possible a typo somewhere in your question? Since $2n^{n+1}/2^n = (n/2)^n \cdot 2n \ge 2n$ there will be no $c_2$ as you want. I'll texify your question, please check if I've done right. –  martini Mar 22 '12 at 9:55
    
@martini is correct. The equation, as written, is false. –  JeffE Mar 22 '12 at 9:59
    
The equation is the one i posted: 2n^n + 2n^(n+1) = 2n^n + θ(2^n) ...where ^ is the power... –  forrestGump Mar 22 '12 at 10:10
    
... and $2n^{n+1}$ isn't a $\Theta$ of $2^n$ as I wrote above ...where is this question from? –  martini Mar 22 '12 at 10:23
    
Ok thanks....the question comes from class material.... –  forrestGump Mar 22 '12 at 10:30
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.