Need help with the concept of O-complexity

khalidh223

New member
Joined
Oct 6, 2019
Messages
5
If f(n) is O(g(n)), then why are there infinitely many choices of c and infinitely choices of n0 that satisfy this definition of O-complexity?:

f(n) is O(g(n)) if, for constants c > 0 and n greater than or equal to 0, f(n) is less than or equal to c * g(n) for all n greater than or equal to 0
 
I don't see n0 in your definition. Is it n > n0?
Do you mean why for specific 2 functions f and g we can use infinitely many constants c and n0 to show that f(n) is O(g(n))?
Let's say we can use 2.5 for c and 23 for n0: f(n) is less than or equal to 2.5*g(n) for n > 23.
But if 2.5 works, wouldn't 2.6 work too? Isn't 2.6*g(n) > 2.5*g(n)? How about 2.7? 2.8? etc. Infinitely many choices.
And what about n > 24? If something is true for n > 23 it's true for n > 24. And n > 25. etc. Infinitely many choices.
 
Top