tags:

views:

28

answers:

2

Am I wondering if the follow are true.

If f(n) is O(g(n)) and f(n) is also Ω(g(n)) that means f(n) is also big Θ(g(n)) right? Also if either of the 2 above are false, then f(n) is not big Θ(g(n))?

A: 

Since big-omega is lower bound, big-O is upper bound, and big-theta is upper and lower bound, it stands to reason yes.

Amber
+1  A: 

If f(n) is O(g(n)) and f(n) is also Ω(g(n)) that means f(n) is also big Θ(g(n)) right?

Yes. That is the definition of big theta.

Also if either of the 2 above are false, then f(n) is not big Θ(g(n))?

Yes. It is a bijection.

if we know f1(n) is Θ(g(n)) and f2 (n) is Θ(g(n)), does that mean f1 (n) + f2 (n) is Θ(g(n)). Why?

Because f1(n) is approximately c1*g(n) and f2 is approximately c2*g(n), so f1(n)+f2(n) is approximately (c1+c2)*g(n), and so any linear combination will preserve that relationship.

Michael Aaron Safyan