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

Answers


dfri February 2016

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)" (or some O(g(n))) just as frequently at the web, at least outside of the scope of scientific articles.

Post Status

Asked in February 2016
Viewed 1,148 times
Voted 12
Answered 1 times

Search




Leave an answer