The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+25 votes

Consider the following three claims

- $(n+k)^m = \Theta(n^m)$ where $k$ and $m$ are constants
- $2^{n+1} = O(2^n)$
- $2^{2n+1} = O(2^n)$

Which of the following claims are correct

- I and II
- I and III
- II and III
- I, II, and III

+25 votes

Best answer

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**

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

+13

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.

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.

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.1k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.1k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 1k
- Others 1.3k
- Admissions 449
- Exam Queries 428
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 8

35,499 questions

42,767 answers

121,499 comments

42,151 users