COT 3400 - Week 2 (Mon): Growth of Functions & Big-O (Lecture Notes)

Vocabulary flashcards covering growth of functions and Big-O concepts from the notes.

Growth of Functions

Study of how an algorithm's running time grows with input size n, focusing on asymptotic behavior rather than exact times.

Big-O Notation (O(g(n)))

A representation of an upper bound on f(n) such that f(n) ≤ c·g(n) for all n ≥ n₀, with constants c > 0 and n0 ≥ 0.

Asymptotic Growth

The behavior of a function as n grows large, ignoring constant factors and lower-order terms.

Upper Bound

An upper limit on the growth rate of a function; Big-O provides this bound.

c (positive constant in Big-O)

A positive constant used in the Big-O inequality f(n) ≤ c·g(n).

n₀ (threshold in Big-O)

A nonnegative threshold from which the Big-O bound holds for all n ≥ n₀.

Drop constants and lower-order terms

In Big-O analysis, ignore constant factors and terms of lower order than the leading term when comparing growth rates.

Dominant (leading) term

The term with the highest growth rate in f(n) as n → ∞; determines the Big-O classification.

Example f(n) = 3n² + 5n + 7

This function is in O(n²) but not in O(n).

Activity: Classification of f(n) = n³ + 2n - O(n²) - O(n³) - O(n⁴)

A practice problem to identify the appropriate Big-O bound by focusing on the dominant growth term.