algorithm analysis - orders of growth question

Question

I'm studing orders of growth "big oh", "big omega", and "big theta". Since I can't type the little symbols for these I will denote them as follows:

ORDER = big oh
OMEGA = big omega
THETA = big theta

For example I'll say n = ORDER(n^2) to mean that the function n is in the order of n^2 (n grows at most as fast n^2).

Ok for the most part I understand these:

n = ORDER(n^2)             //n grows at most as fast as n^2
n^2 = OMEGA(n)             //n^2 grows atleast as fast as n
8n^2 + 1000 = THETA(n^2)   //same order of growth

Ok here comes the example that confuses me:

what is n(n+1) vs n^2

I realize that n(n+1) = n^2 + n; I would say it has the same order of growth as n^2; therefore I would say

n(n+1) = THETA(n^2)

but my question is, would it also be correct to say:

n(n+1) = ORDER(n^2)

please help because this is confusing to me. thanks.

Thank you guys!!

just to make sure I understand correctly, are these all true:

n^2+n = ORDER(2000n^2)
n^2+n = THETA(2000n^2)
n^2+n = OMEGA(2000n^2)

2000n^2 = ORDER(n^2+n)
2000n^2 = THETA(n^2+n)
2000n^2 = OMEGA(n^2+n)

So if f = THETA(g) then f=ORDER(g) and f=OMEGA(g) are also true.

Answer 1

Yes, n(n+1) = Order(n^2) is correct.

If f = Theta(g) then f = Order(g) and g = Order(f) are both true.

Answer 2

Moron is correct, and that is the easiest way to think about it.

But to understand it, return to the definition for f(n) = O(g(n)): there exists a positive M and n0 such that, for all n > n0, f(n) <= Mg(n).

Suppose M=2. Can you find a value, n0, such that for all n > n0, n^2+n <= M(n^2)?

(Plot both functions with pen and paper to understand how they grow in relation to one another.)

Answer 3

You can use this simple table to get an easy and intuitive understanding of what these symbols mean:

If f(n) and g(n) are two functions then

Growth Rate
if f(n) = Θ(g(n))   then     growth rate of f(n) = growth rate of g(n)

if f(n) = O(g(n))   then     growth rate of f(n) ≤ growth rate of g(n)

if f(n) = Ω(g(n))   then     growth rate of f(n) ≥ growth rate of g(n)

if f(n) = o(g(n))   then     growth rate of f(n) < growth rate of g(n)

if f(n) = ω(g(n))   then     growth rate of f(n) > growth rate of g(n)

Also, the order is always written in terms of the highest order i.e if the order is O(n^2 + n + 1) then we simply write it as O(n^2) as n^2 is of the highest order.