coders February 2016
### Big O notation of a constant

I calculate my runtime complexity to be **4**, what is the Big O notation of this?

For example if my runtime complexity is **4 + n** then its Big O = **O(n)**.

Let's look loosely at the definition of what we mean by `f(n) is in O(g(n))`

:

`f(n)`

is in`O(g(n))`

means that`c · g(n)`

is an upper bound on`f(n)`

. Thus there exists some constant`c`

such that`f(n) ≤ c · g(n)`

holds for sufficiently large`n`

(i.e. ,`n ≥ n0`

for some constant`n0`

).

You can treat a constant function just as any other function, w.r.t. analysing its asymptotic behaviour using e.g. big-O notation.

```
f(n) = 4
g(n) = 1
f(n) ≤ c · g(n) = c · 1, for c ≥ 4 and for all n (*)
(*) with e.g. n0=0 and c=4 => f(n) is in O(1)
```

Note: as Ctx notes in the comments below, `O(1)`

(or e.g. `O(n)`

) describes a *set of functions*, so to be fully correct, `f`

should be described to be in `O(1)`

(`f ∈ O(n)`

, `f`

:s set membership in `O(1)`

), rather than *" f(n) being in O(1)"*. You can, however, probably expect to see the less rigorous version

`f(n)`

is in `O(1)`

"`O(g(n))`

) just as frequently at the web, at least outside of the scope of scientific articles.
Asked in February 2016

Viewed 1,148 times

Voted 12

Answered 1 times

Viewed 1,148 times

Voted 12

Answered 1 times