CODEWITHSUNDEEP
runtimebig-otime-complexity
Zimbabaluba
Zimbabaluba

Reputation: 588

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

Upvotes: 1

Views: 5627

Answers (1)

dfrib
dfrib

Reputation: 73196

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.

Upvotes: 1

Related Questions