In first case, $c \geq 2$, So, we can find atleast one positive real 'c' for which definition of Big O will be satisfied.. Right?

The Gateway to Computer Science Excellence

+4 votes

Best answer

> Is $2^{n+1} = O(2^{n})$ ?

- **Yes. **

**- Reason : **$\space 2 \cdot 2^{n} \le c \cdot 2^{n}$ where $c$ is a positive real number, $c \ge 2$ in this particular case.

> Is $2^{2n} = O(2^{n})$ ?

- **No. **

**- Reason : **

$2^{n+n} \le c \cdot 2^{n} $ where c is a positive real number. There's no such constant $c$ that satisfies this inequality.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,376 answers

198,520 comments

105,312 users