The Gateway to Computer Science Excellence

0 votes

If c is non-negative but not infinite then :

1.f(n)=O(g(n))

2.f(n)=⊖(g(n))

According to me :

it is saying that c is non-negative and not infinite so if g(n) tends to zero then c will tend to infinite but it is given that it is not infinite therefore clearly g(n) should be larger than f(n) , so more precisely we can say f(n)=O(g(n)) ,plz correct me ,if I am wrong

0 votes

Given that c is non-negative means that c={0} ∪ {1,2,3...n} and it is also mentioned that it is non-negative so if c=0 ,it implies that f<g and if c >0 then it implies that f =g , so f(n)=O(g(n)) .

0

Consider positive functions as $f(n)=n$ and $g(n)=n^2$ for values of $n>=0$

Now, if C is a positive integer, of course $g(n)$ will be greater than $f(n)$ for all values of C

But, if C is a positive fraction, say $1/1000$ Then for some values of $n$ $g(n)$ will be smaller than $f(n)$

Hence, we have $C_{1} g(n) <= f(n) <= C_{2} g(n)$

Therefore, $f(n) = \Theta g(n)$

0 votes

Consider positive functions as $f(n)=n$ and $g(n)=n^2$ for values of $n>=0$

Now, if C is a positive integer, of course $g(n)$ will be greater than $f(n)$ for all values of C

But, if C is a positive fraction, say $1/1000$ Then for some values of $n$ $g(n)$ will be smaller than $f(n)$

Hence, we have $C1 g(n) <= f(n) <= C2 g(n)$

Therefore, $f(n) = \Theta g(n)$

52,215 questions

60,009 answers

201,234 comments

94,696 users