Menu
A colleague of mine has asked me a question: Is the set o(1) (little o notation) empty?
My question is: Is o(1) an empty set? If not, is there a program that has o(1) time complexity?
Reminder, definition of little-o by Cormen:
A function
f(n)is said to be ino(g(n))if for any positive constantc>0, there exists a constantn0 > 0such that0 <=f(n) < cg(n), for alln>= n0.
Intuitively, if f(n) is in o(g(n)) if it is in O(g(n)), but this bound is NOT tight.
301
The notation o(1) means ``a function that converges to 0. '' This means that there is some input size past which the function is always between -0.1 and 0.1; there is some input size past which the function is always between -0.01 and 0.01; and so on.
An O(1) algorithm means that the execution time of it will be independent of its input. So if the hardware is the same, the algorithm will always take a constant time with any given input. There are plenty of algorithms whose running time does not depend on the size of the input, that is what O(1) means.
An algorithm has constant time complexity if it takes the same time regardless of the number of inputs. ( Reading time: under 1 minute) If an algorithm's time complexity is constant, it means that it will always run in the same amount of time, no matter the input size.
O(1) and Θ(1) aren't necessarily the same if you are talking about functions over real numbers. For example, consider the function f(n) = 1/n. This function is O(1) because for any n ≥ 1, f(n) ≤ 1.
The function f(n)=0 is in o(1) and so o(1) is not empty. Because for every c>0, f(n) < c * 1.
It's a matter of opinion (or definition) whether a program's time complexity can be o(1). If you think that a program can exist with no basic operations then it would have time complexity in o(1). If you think a program can't exist with no basic operations, then it will always take at least 1 time unit no matter the input, and picking c=0.5 in the definition of little-o gives you a proof that its time complexity is not o(1).
72
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
