Asymptotic tight bound question

  • Thread starter Thread starter gr3g1
  • Start date Start date
  • Tags Tags
    Bound
gr3g1
Messages
71
Reaction score
0

Homework Statement



Hi,

I just have a basic question regarding an asymptotic tight bound question.

The question is :
TRUE / FALSE

http://latex.codecogs.com/gif.latex?3^{n+1} \text{ belongs to } \Theta(3^{n})

By definition of big theta:

c_{1}g(n) \leq f(n) \leq c_{2}g(n) \text { } \forall n > n0

So in my case, g(n) = 3^{n} \text{ and } f(n)=3^{n+1}

Therefore to prove this true, I should show a set of values for c1, c2, and n for the definition to hold true.

Is that correct?
 
Last edited by a moderator:
Physics news on Phys.org
anyone?
 
There are two things I don't understand about this problem. First, when finding the nth root of a number, there should in theory be n solutions. However, the formula produces n+1 roots. Here is how. The first root is simply ##\left(r\right)^{\left(\frac{1}{n}\right)}##. Then you multiply this first root by n additional expressions given by the formula, as you go through k=0,1,...n-1. So you end up with n+1 roots, which cannot be correct. Let me illustrate what I mean. For this...
Back
Top