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...If we let c be 3 and n be 1, f(n) = O(n).
~ Sipser
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