in Algorithms edited by
47 votes

Consider the following three claims:

  1. $(n+k)^m = \Theta(n^m)$ where $k$ and $m$ are constants
  2. $2^{n+1} = O(2^n)$
  3. $2^{2n+1} = O(2^n)$

Which of the following claims are correct?

  1. I and II
  2. I and III
  3. II and III
  4. I, II, and III
in Algorithms edited by

1 comment

Hope this will help


3 Answers

51 votes
Best answer

I. Rate of growth of $(n+k)^m$ is same as that of $(n^m)$ as $k$ and $m$ are constants. (If either $k$ or $m$ is a variable then the equality does not hold), i.e., for sufficiently large values of $n,$

$$(n+k)^m \leq a n^m \text{ and}$$

$$n^m \leq b (n+k)^m$$

where $a$ and $b$ are positive constants. Here, $a$ can be $k^m$and $b$ can be $1.$


II. $2^{n+1} = 2\times (2^n) = \Theta\left(2^n\right)$ as $2$ is a constant here.

As $2^{n+1}$ is both upper and lower bounded by $2^n$ we can say $2^{n+1} = O\left(2^n\right).$ $(\Theta$ implies both $O$ as well as $\Omega)$


III. $2^{2n+1}$ has same rate of growth as $2^{2n}$.

$2^{2n} = {2^n}^2 = 2^n \times 2^n$

$2^n$ is upper bounded by $(2^n)^2$, not the other way round as $2^{2n}$ is increasing by a factor of $2^n$ which is not a constant.


Correct Answer: $A$

edited by


It is correct. But the first case is TRUE because m is a constant, had m been a variable, the equality no longer holds.
edited by
ok so (n)^n = O(n+k)^n right ?
I have edited the answer

There is really no need to include the "CORRECT ME IF I AM WRONG" phrase in each of your answers. smiley

@arjun sir, why would the equality change if m is not a constant ?
because $3^n \neq O\left(2^n \right)$.
Sir sometimes we say that in this type of questions take log on both side and compare. so if i take log i then have to compare (2n+1) and n both are asymptotically same right. ??
sometimes "who" says?

When we take $\log$ we get new functions. So, the asymptotic complaxities of the new functions need not be same as those of the original functions - because asymptotic compalixites ignore constants and $\log$ function can make new constants to function. So, if you are taking $\log$ this needs to be considered separately.

What would be the relation here ?

(n+k)p and np  where n and K are constant and p is a variable?


what is the relation between these two:

(N+K)p   and Np  where N , K are constant while p is variable.?

edited by

n, m: variable and k: constant

(n + k)m  = nm + mc1.nm-1.k + mc2.nm-2.k2mc3.nm-3.k3+ .... + + km


General term:

         mcr is max when r -> m/2, so we can have mcm/2 = O(mm/2)

So we can write above expression as:

        = O(mm/2.(nm + km))

        = O(mm/2. nm+1 ) ; coz  km = O(nm) and nm O(nm+1

Is this correct?

If it is, then can we have even tighter upper bound?

edited by

@Arjun sir


Please check if my above approach is correct.

PS. I was trying to add the answer as a reply to the Arjun sir's first comment- "It is correct. But the first case is TRUE because m is a constant...."

But it is being sent at the end after all the comments.

@moulin Not sure how that does the proof. And with $\Theta$ we already have the tightest bound. You can see the answer now.

@Arjun sir

I am sorry if I wasn't clear.

I read the updated answer and I have changed the question a bit in response to your comment that "If either k or m is a variable then the equality (n+k)= Θ(nm) does not hold".

So if n, m are variables and only k is constant, then what will be the relation?

Now we can't ignore the mcr term that will come in expansion of (n+k)m as 'm' is a variable.

For this case I have calculated, (n+k)m O(mm/2. nm+1 ) as the answer.

Is my method and/or answer correct for this particular case?

P.S. Sometimes I feel I am asking for quite valuable from you guys and I don't feel comfortable about it. You and others are already doing so much for this amazing platform.

\[2^{2n} = 4^{n} Right..?\]

@Punit Sharma Yeah, you are right on $2^{2n} = 4^{n}$. In the above question it is much easier to think this way.

so sir how can we find out when to take log and when to not take log?
0 votes


Which is true by considering leading ordered term present in polynomial expression.

2n×2n can't be written as Θ(2n)
So, this is False.

0 votes
  1.  (n+k)^m where m and k are constants, on expanding this equation first term we get n^m.                                    (n+k)^m<=cn^m  where c is constant                                                                                                              (n+k)^m=Θ(n^m)                                                                                                                                                     
  2. 2^(n+1)=2*2^n=c*2^n {let c=2}                                                                                                                         2^(n+1)=O(2^n)                                                                                                                                                           
  3. 2^(2n+1)=((2^n)^2)*2=c*(2^n)^2 {let c=2}                                                                                                           2^(2n+1) is not has same rate of growth O(2^2n)                                                                                                                                                                                                                                                            Option A is right                                                                                                                    
edited by

Related questions