O ( 1 ) O(1) is love, O ( 1 ) O(1) is life

True or false :

If a code has O ( 1 ) O(1) time complexity, then the runtime of the code is exactly the same for all possible inputs (intended inputs).

Notation :

True False

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Prasun Biswas
Dec 29, 2015

O ( 1 ) O(1) time is also called "constant time" but this term is a misnomer. O ( 1 ) O(1) time doesn't imply that the runtime is constant, it implies that the runtime can be bounded above by a constant (mathematical definition), i.e., if S S is the set of all possible runtimes (in seconds) of the code, then,

Code is O ( 1 ) k R + sup ( S ) = k \text{Code is }O(1)\iff \exists k\in\Bbb{R^+}~\mid \sup(S)=k

This means that the code need not have the same runtime for all possible inputs but that the set of all possible runtimes of the code for all inputs has a supremum (the supremum would be a positive real because runtime is always a positive real).

Consider the following code as an example (in Python 3):

1
2
3
4
5
from time import sleep
n=int(input())
if n==1:
    sleep(30)
print("Hello world!")

For the above code, the intended inputs are integers. When the code is executed, if the input is n=1 , it waits for 30 seconds and then prints "Hello world!", otherwise it prints "Hello world!" straightaway.

So, assuming that printing happens in an instant, for integer inputs other than 1 1 , the runtime is 0 secs (instant) but for n=1 , the runtime is 30 secs.

So, the runtime is bounded above by any k k\geq 30 secs, i.e., the supremum of the set of runtimes of the above code is 30, a constant, hence the code is O ( 1 ) O(1) by definition.

Moderator note:

Indeed. Something else to point out is that the runtime doesn't need to be increasing for large n n . Extending Parsun's code, we can create a program that has a long run time for small integers, and a short run time otherwise.

I hope you don't refer to Shrek in the title...

Arulx Z - 5 years, 5 months ago

Log in to reply

Haha, it's actually a meme by now : "X is love, X is life". Makes for a catchy title, doesn't it? :D

Prasun Biswas - 5 years, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...