algorithm analysis - orders of growth question

Posted by cchampion on Stack Overflow See other posts from Stack Overflow or by cchampion
Published on 2010-06-06T22:02:38Z Indexed on 2010/06/06 22:12 UTC
Read the original article Hit count: 572

Filed under:
|

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.

© Stack Overflow or respective owner

Related posts about algorithm

Related posts about homework