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.
Asked in February 2016Viewed 1,148 timesVoted 12Answered 1 times