1.7k 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
edited | 1.7k views

1) Clearly rate of growth of $(n+k)^m = n^m$ as $k$ and $m$ are constants

so TRUE

2) $2^{n+1} = 2*(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)$

so TRUE

3) $2^{2n+1}$ has same rate of growth as $2^{2n}$

$2^{2n} = {2^n}^2$

$2^n$ is upper bounded by $(2^n)^2$, not the other way round

so FALSE

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

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

0
@arjun sir, why would the equality change if m is not a constant ?
+2
because $3^n \neq O\left(2^n \right)$.
0
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. ??
+5
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.
0

What would be the relation here ?

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

0

what is the relation between these two:

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