11,495 views

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

1 comment

Hope this will help

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

So, TRUE.

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

So, TRUE.

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.

So, FALSE.

Correct Answer: $A$

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 ?

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

@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+ .... + mcm-1.n.km-1 + km

General term: mcr.nm-r.kr

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?

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

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

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