Wednesday, October 18, 2006

time complexity

f(n) <= c g(n)

Intuitively, f(n) = O(g(n)) means that f is less than or equal to g if we disregard difference up to a constant factor. You may think of O as representing a suppressed constant...

~ Sipser
If we let c be 3 and n be 1, f(n) = O(n).

If we let c be 1 and n be 85, disregarding the coefficient still gives a function in linear time.

It's a matter of definition.

No comments:

Post a Comment