edited by
18,420 views
53 votes
53 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
edited by

3 Answers

Best answer
57 votes
57 votes

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$

edited by
1 votes
1 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
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
Answer:

Related questions

50 votes
50 votes
11 answers
4
Kathleen asked Sep 17, 2014
14,103 views
The following are the starting and ending times of activities $A, B, C, D, E, F, G$ and $H$ respectively in chronological order: $“a_s \: b_s \: c_s \: a_e \: d_s \: c_...