The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+26 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
asked in Algorithms by Veteran (59.5k points)
edited by | 2k views

1 Answer

+27 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.


answered by Active (3.8k points)
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.
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.?


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?


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


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,039 questions
45,533 answers
48,848 users