What Does The Little O Mean In Functions?

In functions, the "little o" notation, written as o(g(x))o open paren g of x close paren 𝑜(𝑔(𝑥))

, is a way to describe the asymptotic behavior of a function f(x)f of x

𝑓(𝑥)

. Specifically, f(x)=o(g(x))f of x equals o open paren g of x close paren

𝑓(𝑥)=𝑜(𝑔(𝑥))

means that f(x)f of x

𝑓(𝑥)

grows strictly slower than g(x)g of x

𝑔(𝑥)

as xx

𝑥

approaches a certain limit, often infinity. Intuitively, it signifies that f(x)f of x

𝑓(𝑥)

becomes insignificant or negligible in comparison to g(x)g of x

𝑔(𝑥)

as the input gets very large.

Formal definition

For two functions, f(x)f of x

𝑓(𝑥)

and g(x)g of x

𝑔(𝑥)

, we say that f(x)=o(g(x))f of x equals o open paren g of x close paren

𝑓(𝑥)=𝑜(𝑔(𝑥))

as x→∞x right arrow infinity

𝑥→∞

if for every positive constant c>0c is greater than 0

𝑐>0

, there exists a constant x0x sub 0

𝑥0

such that:|f(x)|<c|g(x)|the absolute value of f of x end-absolute-value is less than c the absolute value of g of x end-absolute-value

|𝑓(𝑥)|<𝑐|𝑔(𝑥)|

for all x≥x0x is greater than or equal to x sub 0

𝑥≥𝑥0

.

This definition is equivalent to the limit definition, which states that the ratio of the two functions approaches zero as xx

𝑥

tends to infinity:limx→∞f(x)g(x)=0limit over x right arrow infinity of f of x over g of x end-fraction equals 0

lim𝑥→∞𝑓(𝑥)𝑔(𝑥)=0

The notation can also be used for limits as xx

𝑥

approaches a finite value, aa

𝑎

. In this case, f(x)=o(g(x))f of x equals o open paren g of x close paren

𝑓(𝑥)=𝑜(𝑔(𝑥))

as x→ax right arrow a

𝑥→𝑎

if:limx→af(x)g(x)=0limit over x right arrow a of f of x over g of x end-fraction equals 0

lim𝑥→𝑎𝑓(𝑥)𝑔(𝑥)=0

Little-o versus big-O notation

To fully grasp the meaning of little-o, it's essential to understand its relationship with big-O notation, O(g(x))cap O open paren g of x close paren

𝑂(𝑔(𝑥))

, and the key distinction between them.

Feature	Little-o (o(g(x))o open paren g of x close paren 𝑜(𝑔(𝑥)) )	Big-O (O(g(x))cap O open paren g of x close paren 𝑂(𝑔(𝑥)) )
Growth rate	f(x)f of x 𝑓(𝑥) grows strictly slower than g(x)g of x 𝑔(𝑥) .	f(x)f of x 𝑓(𝑥) grows at most as fast as g(x)g of x 𝑔(𝑥) .
Analogy	Like a "strictly less than" relation (f<gf is less than g 𝑓<𝑔 ).	Like a "less than or equal to" relation (f≤gf is less than or equal to g 𝑓≤𝑔 ).
Bound tightness	Not an asymptotically tight upper bound.	Can be an asymptotically tight upper bound.
Example	n=o(n2)n equals o open paren n squared close paren 𝑛=𝑜(𝑛2) because nn 𝑛 grows strictly slower than n2n squared 𝑛2 .	3n2+4n=O(n2)3 n squared plus 4 n equals cap O open paren n squared close paren 3𝑛2+4𝑛=𝑂(𝑛2) because the dominant term, n2n squared 𝑛2 , is of the same order.
Example (strictness)	3n2+4n3 n squared plus 4 n 3𝑛2+4𝑛 is noto(n2)o open paren n squared close paren 𝑜(𝑛2) because it grows at the same rate as n2n squared 𝑛2 .	3n2+4n3 n squared plus 4 n 3𝑛2+4𝑛 isO(n2)cap O open paren n squared close paren 𝑂(𝑛2) .

Examples of little-o notation

Example 1: Comparing polynomials

Question: Is f(n)=100n2+50nf of n equals 100 n squared plus 50 n

𝑓(𝑛)=100𝑛2+50𝑛

in o(n3)o open paren n cubed close paren

𝑜(𝑛3)

?Analysis: We use the limit definition:limn→∞100n2+50nn3=limn→∞100n+50n2=0limit over n right arrow infinity of the fraction with numerator 100 n squared plus 50 n and denominator n cubed end-fraction equals limit over n right arrow infinity of 100 over n end-fraction plus the fraction with numerator 50 and denominator n squared end-fraction equals 0

lim𝑛→∞100𝑛2+50𝑛𝑛3=lim𝑛→∞100𝑛+50𝑛2=0

Conclusion: Since the limit is 0, 100n2+50n=o(n3)100 n squared plus 50 n equals o open paren n cubed close paren

100𝑛2+50𝑛=𝑜(𝑛3)

. This confirms that a quadratic function grows strictly slower than a cubic function.

Example 2: Comparing a function with itself

Question: Is f(n)=3n2f of n equals 3 n squared

𝑓(𝑛)=3𝑛2

in o(n2)o open paren n squared close paren

𝑜(𝑛2)

?Analysis: Using the limit definition:limn→∞3n2n2=3limit over n right arrow infinity of the fraction with numerator 3 n squared and denominator n squared end-fraction equals 3

lim𝑛→∞3𝑛2𝑛2=3

Conclusion: The limit is 3, not 0. Therefore, 3n23 n squared

3𝑛2

is not o(n2)o open paren n squared close paren

𝑜(𝑛2)

. This reinforces that little-o denotes a strictly slower growth rate.

Example 3: Expressing function behavior near a point

Little-o is not only for limits at infinity. It's used in calculus to approximate functions, such as in the definition of a derivative.

The statement that a function ff

𝑓

is differentiable at point aa

𝑎

with derivative f′(a)f prime of a

𝑓′(𝑎)

can be expressed using little-o:f(a+h)=f(a)+f′(a)h+o(h)f of open paren a plus h close paren equals f of a plus f prime of a h plus o open paren h close paren

𝑓(𝑎+ℎ)=𝑓(𝑎)+𝑓′(𝑎)ℎ+𝑜(ℎ)

as h→0h right arrow 0

ℎ→0

.

This means that the remainder term, f(a+h)−f(a)−f′(a)hf of open paren a plus h close paren minus f of a minus f prime of a h

𝑓(𝑎+ℎ)−𝑓(𝑎)−𝑓′(𝑎)ℎ

, is an unspecified function that goes to zero faster than hh

ℎ

. In other words:limh→0f(a+h)−f(a)−f′(a)hh=0limit over h right arrow 0 of the fraction with numerator f of open paren a plus h close paren minus f of a minus f prime of a h and denominator h end-fraction equals 0

limℎ→0𝑓(𝑎+ℎ)−𝑓(𝑎)−𝑓′(𝑎)ℎℎ=0

Rearranging this gives the standard definition of a derivative:limh→0f(a+h)−f(a)h=f′(a)limit over h right arrow 0 of the fraction with numerator f of open paren a plus h close paren minus f of a and denominator h end-fraction equals f prime of a

limℎ→0𝑓(𝑎+ℎ)−𝑓(𝑎)ℎ=𝑓′(𝑎)

Applications in computer science and mathematics

• Algorithm analysis: In computer science, little-o can describe an algorithm's runtime, indicating a loose upper bound that isn't tight. This is useful when the exact complexity is very difficult to pin down but is known to be strictly less than a certain function. For example, a fast algorithm might have a runtime that is o(n2)o open paren n squared close paren

  𝑜(𝑛2)

  , even if its tight bound is more complex.

• Approximations: In mathematics, little-o is a powerful tool for expressing approximations, particularly in Taylor series expansions. It provides a concise way to represent an error term that becomes negligible as a variable approaches a certain value.

• Probability and statistics: Little-o notation is used in analyzing the asymptotic behavior of estimators and other statistical quantities, showing when one term becomes dominated by another as the sample size grows.