Big-O: The Formal Definition

An upper bound on growth

Big-O gives an asymptotic upper bound. Formally, f(n) = O(g(n)) if there exist positive constants c and n₀ such that f(n) ≤ c · g(n) for all n ≥ n₀. In words: beyond some point, f never grows faster than a constant multiple of g. Two consequences make Big-O practical. Constant factors disappear: 5n and 0.1n are both O(n), because the constant c absorbs them. Lower-order terms disappear: 3n² + 10n + 50 is O(n²), because for large n the n² term dominates. Proofs pick concrete constants: for 3n² + 10n + 50, choose n₀ = 10; then 10n ≤ n² and 50 ≤ n², so f(n) ≤ 3n² + n² + n² = 5n², giving c = 5. Note that Big-O is an upper bound, so it is technically true that n = O(n²), though not useful; in practice we state the tightest simple bound we can justify. The notation "f(n) = O(g(n))" is conventional shorthand for "f belongs to the set O(g(n))".

f stays under c·g after n₀

Big-O means that beyond some point n₀, f(n) never rises above a constant multiple of g(n).

Proving a bound by choosing constants

Show that f(n) = 3n² + 10n + 50 is O(n²).

goal: find c > 0 and n0 such that 3n^2 + 10n + 50 <= c * n^2 for all n >= n0

for n >= 10:
  10n <= n^2          (because n >= 10)
  50  <= n^2          (because n^2 >= 100)
so  3n^2 + 10n + 50 <= 3n^2 + n^2 + n^2 = 5n^2

choose c = 5, n0 = 10  ->  f(n) = O(n^2)

non-example: n^2 is NOT O(n), because n^2 <= c*n fails for every n > c

Big-O is not "worst case"

Big-O is a bound on a function; worst case is a choice of which function you analyse. You can give a Big-O bound for the best case or the average case too. Saying "Big-O means worst case" is a common interview slip.

त्वरित जाँच: Which statement is true by the definition of Big-O?

• 2n + 100 is O(1)
• n³ is O(n²)
• 7n² + n is O(n²)
• n log n is O(n)