Asymptotic Running Time of Algorithms - Formal Definition of big-O Notation - leading term analysis

Q: How do you prove that f(n) = O(g(n))?

Find constants c and n0 such that f(n) ≤ c·g(n) for all n > n0. The pair (c, n0) is called a witness pair.

Oct 14, 2026

Upload by Franzy

Asymptotic running time analysis explains how to classify algorithm efficiency using big-O notation. It formalizes the definition of f(n) being O(g(n)) via constants and a witness pair (c, n0), and shows examples including linear versus quadratic growth. The notes then guide leading-term comparison, log-base invariance, and how to count basic operations in the RAM model, while emphasizing that lower-order terms and irrelevant work can be ignored for asymptotic results.

LanguageEnglish

CategoryPresentations

FormatPDF

Pages8

Reading Time3 min

AccessFree to download

Formal Definition of big-O Notation

Asymptotic Complexity: leading term analysis

What are the basic OPERATIONS?

Why is Asymptotic Complexity so important?

What Operations Should We Count?

Remarks on counting operations

Analysis of Merge-Sort

Asymptotic Running Time of Algorithms Formal Definition of big-O Notation: • Let f(n) and g(n) be functions. We say f(n) is of order g(n), written O(g(n)), if there is a constant c > 0 such that for all but a finite number of positive values of n: f(n) ≤ c * g(n) In other words, sooner or later g(n) overtakes f(n) as n gets large. • Example: f(n) = n+5; g(n) = n. Show that f(n) = O(g(n)) . Choose c = 6: f(n) = n+5 ≤ 6*n for all n > 0. • Example: f(n) = 17n; g(n) = 3n2 . Show that f(n) = O(g(n)) . Choose c = 6: f(n) = 17n ≤ 6 * 3n2 for all n > 0. Asymptotic Complexity: leading term analysis • Comparing searching and sorting algorithms so far: – Count worst-case number of comparisons as function of array size. – Drop lower-order terms, floors/ceilings, and constants to come up with asymptotic running time of algorithm. • We will now generalize this approach to other programs: – Count worst-case number of operations executed by program as a function of input size. – Formalize definition of big-O complexity to derive asymptotic running time of algorithm. • To prove that f(n) = O(g(n)), find an n0 and c such that f(n) ≤ c * g(n) for all n > n0 . • We will call the pair (c, n0) a witness pair for proving that f(n) = O(g(n)). • For asymptotic complexity, base of logarithms does not matter. • Let us show that log2(n) = O(logb(n)) for any b > 1. • Need to find a witness pair (c, n0) such that: log2(n) ≤ c * logb (n) for all n > n0. • Choose (c = log2 (b), n0 = 0). • This works because c * logb(n) = log2(b) * logb(n) = log2(blogb(n)) = log2(n) for all positive n. What are the basic OPERATIONS? • For searching and sorting algorithms, you can usually determine big-O complexity by counting comparisons. • Why? • Usually end up doing some fixed number of arithmetic and/or logical operations per comparison. • Why don’t we count swaps for sorting? – e.g., think about selection sort: • max of n swaps • but must do O(n2 ) comparisons • swaps and comparisons have similar cost • Is counting number of comparisons always right? – No. – e.g., selection sort on linked lists instead of arrays Why is Asymptotic Complexity So Important? • Asymptotic complexity gives an idea of how rapidly the space/time requirements grow as problem size increases. • Suppose we have a computing device that can execute 1000 complex operations per second. Here is the size problem that can be solved ina second, a minute, and an hour by algorithms of different asymptotic complexity: | Complexity | 1 second | 1 minute | 1 hour | | --- | --- | --- | --- | | n | 1000 | 60,000 | 3,600,000 | | n log n | 140 | 4893 | 200,000 | | n2 | 31 | 244 | 1897 | | 3n2 | 18 | 144 | 1096 | | n3 | 10 | 39 | 153 | | 2n | 9 | 15 | 21 | What Operations Should We Count? • Must do a detailed counting of all executed operations. • Estimate number of primitive operations that RAM model (basic microprocessor) must do to run program: – Basic operation: arithmetic/logical operations count as 1 operation. • even though adds, multiplies, and divides don’t (usually) cost the same – Assignment: counts as 1 operation. • operation count of righthand side of expression is determined separately. – Loop: number of operations per iteration * number of loop iterations. – Method invocation: number of operations executed in the invoked method. • ignore costs of building stack frames,… – Recursion: same as method invocation, but harder to reason about. – Ignoring garbage collection, memory hierarchy (caches),… | Example: Selection Sort
public static void selectionSort(Comparable[] a) { //array of size n | | | --- | --- | | for (int i = 0; i < a.length; i++) { int MinPos = i;
for (int j = i+1; j < a.length; j++) { if (a[j].compareTo(a[MinPos]) < 0)
MinPos = j;} Comparable temp = a[i];
a[i] = a[MinPos]; a[MinPos] = temp;}} | < --cost = c1, n times
< --cost = c2, n times
< --cost = c3, n*(n-1

FAQs

How do you prove that f(n) = O(g(n))?

Find constants c and n0 such that f(n) ≤ c·g(n) for all n > n0. The pair (c, n0) is called a witness pair.

Why can lower-order terms, floors/ceilings, and constants be ignored?

Asymptotic running time focuses on growth as n becomes large. Once the leading term dominates, those details do not change the big-O classification.

What basic operations are commonly counted when analyzing searching and sorting?

For searching and sorting algorithms, big-O is usually determined by counting worst-case comparisons. Typically, each comparison triggers a fixed number of primitive arithmetic/logical operations.

Oct 14, 2026

Upload by Franzy