The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+24 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 (69k points)
edited by | 1.5k views

1 Answer

+25 votes
Best answer

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


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


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


answered by Loyal (3.9k 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.?

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

33,687 questions
40,230 answers
38,793 users