Complexity and O-Notation

Nievergelt & Hinrichs · Ch. 1 · Algorithms and Data Structures

An algorithm's cost is not a single number. It is a growth rate: how the cost scales as the input grows. Big-O, big-Omega, and big-Theta classify these rates. They let you compare algorithms without benchmarking.

Big-O: upper bounds

f(n) is O(g(n)) if there exist constants c and n_0 such that f(n) ≤ c · g(n) for all n ≥ n_0. It says: f grows no faster than g.

Scheme

; Demonstrate O-notation: compare growth rates
; f(n) = 3n + 5 is O(n) because 3n + 5 <= 4n for n >= 5

(define (f n) (+ (* 3 n) 5))
(define (g n) (* 4 n))

(display "n	f(n)	4n	f<=4n?") (newline)
(define (check n)
  (display n) (display "	")
  (display (f n)) (display "	")
  (display (g n)) (display "	")
  (display (<= (f n) (g n))) (newline))

(check 1)
(check 5)
(check 10)
(check 100)
(check 1000)

Big-Omega and Big-Theta

Big-Omega is the mirror: f(n) is Ω(g(n)) if f grows at least as fast as g. Big-Theta is the sandwich: f(n) is Θ(g(n)) when both O and Ω hold. It means f and g grow at exactly the same rate.

Scheme

; Big-Theta: f(n) = 2n^2 + 3n is Theta(n^2)
; Upper bound: 2n^2 + 3n <= 3n^2 for n >= 3
; Lower bound: 2n^2 + 3n >= 2n^2 for all n

(define (f n) (+ (* 2 n n) (* 3 n)))

(display "n	f(n)	2n^2	3n^2	sandwich?") (newline)
(define (check n)
  (let ((fn (f n))
        (lo (* 2 n n))
        (hi (* 3 n n)))
    (display n) (display "	")
    (display fn) (display "	")
    (display lo) (display "	")
    (display hi) (display "	")
    (display (and (>= fn lo) (<= fn hi))) (newline)))

(check 1)
(check 3)
(check 10)
(check 100)

Comparing growth rates

The hierarchy: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ). An algorithm in a lower class will always win for large enough n, regardless of constant factors.

Scheme

; Growth rate comparison at n = 1000
(define n 1000)

(display "O(1)       = 1") (newline)
(display "O(log n)   = ")
(display (inexact->exact (round (/ (log n) (log 2))))) (newline)
(display "O(n)       = ")
(display n) (newline)
(display "O(n log n) = ")
(display (inexact->exact (round (* n (/ (log n) (log 2)))))) (newline)
(display "O(n^2)     = ")
(display (* n n)) (newline)
(display "O(2^n)     = way too big to print")

Neighbors

Cross-references

🔢 Discrete Math Ch.1 — counting: the combinatorics behind growth rates

by june.kim Recursion →