True or false :
If a code has time complexity, then the runtime of the code is exactly the same for all possible inputs (intended inputs).
Notation :
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.
O ( 1 ) time is also called "constant time" but this term is a misnomer. 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 is the set of all possible runtimes (in seconds) of the code, then,
Code is O ( 1 ) ⟺ ∃ k ∈ R + ∣ 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):
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 , the runtime is 0 secs (instant) but for
n=1
, the runtime is 30 secs.So, the runtime is bounded above by any k ≥ 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 ) by definition.