Hey.

Please edit it more properly.

Please edit it more properly.

The Gateway to Computer Science Excellence

0 votes

Its not at all true.

For example: Take an algorithm which takes $2n$ steps and an another algorithm $B$ which takes $n$ steps. Then their ratio is constant.

But the ratio of $2^{2n}$ and $2^n$ is not at all constant.

So, it is definitely not true.

For example: Take an algorithm which takes $2n$ steps and an another algorithm $B$ which takes $n$ steps. Then their ratio is constant.

But the ratio of $2^{2n}$ and $2^n$ is not at all constant.

So, it is definitely not true.

0 votes

It is not true because

let,f(n)=5n+1 then g(n) will be equalto 'n' i.e.,5n+1=O(n)

but, 2^(5n+1) isnot equal toO(2^n)

let,f(n)=5n+1 then g(n) will be equalto 'n' i.e.,5n+1=O(n)

but, 2^(5n+1) isnot equal toO(2^n)

0 votes

If $f(n)=O(g(n)),$ Then It means that

$f(n)\leq C_{0}. g(n)$; Where $C_{0}$ is constant, $C_{0} > 0,$$n \geqslant n_{0} ,$ and $n_{0}\geq 1$

$2^{f(n)}\leq 2^{(C_{0}.g(n))}$ ;Raising power to both side ----------- 1

If $2^{f(n)}=O(2^{g(n)}),$ Then it means that

$2^{f(n)}\leq C_1.2^{g(n)}$ ;Where $C_{1}$ is constant, $C_{1} > 0,$$n \geqslant n_{0} ,$ and $n_{0}\geq 1$

$2^{f(n)}\leq C_1.2^{g(n)}$ -------------2

Since 1 & 2 are not the same, Then we can say that it's not true.

$f(n)\leq C_{0}. g(n)$; Where $C_{0}$ is constant, $C_{0} > 0,$$n \geqslant n_{0} ,$ and $n_{0}\geq 1$

$2^{f(n)}\leq 2^{(C_{0}.g(n))}$ ;Raising power to both side ----------- 1

If $2^{f(n)}=O(2^{g(n)}),$ Then it means that

$2^{f(n)}\leq C_1.2^{g(n)}$ ;Where $C_{1}$ is constant, $C_{1} > 0,$$n \geqslant n_{0} ,$ and $n_{0}\geq 1$

$2^{f(n)}\leq C_1.2^{g(n)}$ -------------2

Since 1 & 2 are not the same, Then we can say that it's not true.

- 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,519 comments

105,311 users