2,027 views
0 votes
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

3 Answers

0 votes
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 votes
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)$

Related questions

1 votes
1 votes
3 answers
1
3 votes
3 votes
1 answer
3
gate-17 asked Aug 7, 2016
2,807 views
consider the following functions f(n)=log*(log n) , g(n)=log(log* n) relations between these 2 function. please help
7 votes
7 votes
2 answers
4
anshul namdeo asked Jun 6, 2016
12,696 views
Which of the following is true? a. h(n) is O(f(n)) b. h(n) is O(g(n)) c. g(n) is not O(f(n)) d. f(n) is O(g(n))Why not answer c because both f(n) and g(n) have of same or...