Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is there any function that is in o(1)?

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 in o(g(n)) if for any positive constant c>0, there exists a constant n0 > 0 such that 0 <=f(n) < cg(n) , for all n>= n0.

Intuitively, if f(n) is in o(g(n)) if it is in O(g(n)), but this bound is NOT tight.

like image 301
amit Avatar asked May 05 '15 11:05

amit


People also ask

What is the function O 1?

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.

Are there any O 1 algorithms?

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.

What does complexity O 1 mean?

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.

Does O 1 imply theta 1?

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.


1 Answers

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).

like image 72
Paul Hankin Avatar answered Sep 28 '22 12:09

Paul Hankin