Alex Rivera | Logout

Help with big O notation

Asked 2010-07-27T19:24:55.777
9

I've been having some problems trying to grasp the concept of big O notation. So, by definition big O is as follows, T(n) ∈ O(G(n)) if T(n) <= G(n) * C.

Since the the constant "C" can be any integer > 0, wouldn't this following example be true as well?

Example:

n log n ∈ O(log n)
n log n <= log n * c

Where C is equal to the value of n.

I know that the answer is that n log n ∉ O(log n) but I don't understand how since C can be any constant.

Thanks in advance for your help :D

algorithm time-complexity big-o
Edit
Report

1 Answer

1

in the expression n log n, you can't compare the outside n to C, like you are doing. That would be like taking the algrebraic expression x(x+1) and replacing one of the x's with a constant.

In n log n, n is a variable. In the big O expresion, C is a constant.

answered 2010-07-27T19:29:58.993

Your Answer