Redirected
retagged by
594 views
0 votes
0 votes

Any condition for f(n) and g(n) or any value we can take??? I m confused becoz in big oh right side part must b greater than equal ??

retagged by

5 Answers

1 votes
1 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)
0 votes
0 votes
For sure any value and any conditions may not satisfy the equation f(n) = O(g(n))

Coremen says,

if f(n) = O(g(n)) then,

$0 <= f(n) <= c.g(n) $ n>n0\\ ,  c and n0 is constant

i.e. f(n) is aymptotically bounded by g(n)

so if g(n) >= f(n) then

2^g(n) will also be greater then 2^f(n)

 

/* Answered what I understood from the question */
0 votes
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.
0 votes
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.

Related questions

4 votes
4 votes
1 answer
1
Manish Chetwani asked Oct 23, 2017
357 views
What will be the Big Oh for $n!$ ?As we can deduce log($n!$) = O(log n) .Is there any proof like we have for log($n!$) ?
3 votes
3 votes
3 answers
2
Sayan Das 1 asked Sep 21, 2016
778 views
0 votes
0 votes
1 answer
3
0 votes
0 votes
1 answer
4
Deepalitrapti asked Aug 27, 2018
286 views
Condition satisfies or not