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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.6k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,650 questions

56,193 answers

193,988 comments

94,863 users