I have an assignment that is to prove if these are True or False:
I could do B and C to Big-O. Can anyone help with solving Big-Omega and Big-Theta?
(Not looking for answers, but for learning how-to).
A function f is Omega(g) if and only if there exist n0 and c greater than zero such that for n >= n0, f(n) >= c*g(n).
A function f is Big-Oh(g) if and only if there exist n0 and c greater than zero such that for n >= n0, f(n) <= c*g(n).
A function f is Theta(g) if and only if f is both Omega(g) and Big-Oh(g).
(a) 150n^3 + 43n^2 + 50n + 3 is not Omega(n^5) because the high-order term, 150n^3, grows asymptotically slower than n^5, since the power is smaller.
(b) n^10 + 30n^8 + 80n^6 is O(n^12) because the high-order term, n^10, grows asymptotically slower than n^5, since the power is smaller.
(c) 55n + 30 is O(n log n), because the high-order term 55n grows more slowly than nlog(n), because eventually the log(n) term becomes much larger than 55 (for values of n > 2^55, specifically).
(d) n^4 + 4 n^3 + 6 n^2 + n log n is not Theta(2n) because the high-order term n^4 grows more quickly asymptotically than 2n since the power is bigger. Neither is it Theta(2^n), if that's what you actually meant, because n^4 grows asymptotically slower than 2^n.
(e) 9n^2 log n + 40n^2 + 3n is Omega(n^2 log n) because the high-order term 9n^2log(n) grows precisely as fast asymptotically speaking as n^2 log n.
All of these statements can be proven from definitions if necessary, just please let me know if there's an example or two you'd like to see worked.