edited by
680 views
0 votes
0 votes
If there are 2 functions say f(x) and g(x) then is it possible that both conditions:

1) f = o(g)   ............small-oh

2) f = $\omega$(g)    ......little omega

are satisfied at the same time?

The example which I thought of is let f(x)=x and g(x)=x+1

Now, for x>=2 or x>1

I can have:

1)   f(x) > $\frac{1}{2}$g(x)

2)  f(x) < 2.g(x)

This means I can have    c1.g < f  < c2.g  for which we have no asymptotic notation.

Please help if I am going wrong somewhere.
edited by

1 Answer

0 votes
0 votes

For non-negative functions, f(n) and g(n)f(n) is theta of g(n) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)). This is denoted as "f(n) = Θ(g(n))".

This is basically saying that the function, f(n) is bounded both from the top and bottom by the same function, g(n).

Related questions

0 votes
0 votes
2 answers
2
shubhamkks1005 asked Sep 21, 2019
475 views
F(n)=O{ [ f(n)]^2}This statement is true or false With reason..