GATE CSE 2003 | Question: 20

Question

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?

• A. I and II
• B. I and III
• C. II and III
• D. I, II, and III

Comments

@Abhrajyoti00   bhai   2ND OPTION ni samaj aa ra mere...

---

@jugnu1337

2. LHS : $2^{n+1}$ = $2^n.2$ ; RHS : $2^n$

Cancelling $2^n$ from both sides, $2 = 1$ which is true in terms of asymptotic notations. Thus  $2^{n+1}$ = O($2^n$) is TRUE

---

For those of you who are wondering in expression I, why is it okay to ignore k in determining asymptotic order of growth,

using binomial theorem the resultant expression would be =n^m+ mC1. n^(m-1) . k+ mC2. n^(m-2) . k^2 +….+ k^m

since k and m are constants the expression is equivalent to = 1. n^m + c1 n^ (m-1) + c2 n^(m-2)+….+ c

therefore n^m overpowers the lower orders of n asymptotically.

Answer 1

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$

Comments

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

---

Depends upon the parenthesization

Answer 2

 

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

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

Answer 3

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