The Gateway to Computer Science Excellence
0 votes
Is $2^{n+1} = O(2^n) $? $2^{2n} = O(2^n)$$?$
in Algorithms by Boss (41.9k points) | 53 views

1 Answer

+4 votes
Best answer

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


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


by Active (1.6k points)
selected by
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?
bro, you have written "c=2 in this particular case". it can be 3,4,5,...

Yes. You're right. It can be 3, 4, 5... etc. I stopped after 2 since we need only one. I'll edit the answer anyways. Thank you for pointing it out :p

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
50,647 questions
56,492 answers
100,756 users