Big-O, Sorting Algorithms, Data Structures, and Analysis Techniques

Big-O definition

A function f(n) is in O(g(n)) if ∃ c,n0>0 such that f(n) ≤ c·g(n) for all n ≥ n0.

Formal Big-O proof template

For a polynomial f(n)=a_k n^k+...+a_0, note n^i ≤ n^k for n≥1; choose c=Σa_i, n0=1 ⇒ f(n) ≤ c·n^k.

Example Big-O proof

For f(n)=2n^2+3n+3, when n≥3 we have f(n) ≤ 4n^2 ⇒ c=4, n0=3 ⇒ O(n^2).

Amortized analysis definition

Analyzes average cost per operation over any sequence of n operations (no probability assumptions).

Vector push_back doubling

Resizes at 1,2,4,...,n; copies <2n; plus n writes ⇒ total <3n ⇒ amortized O(1).

Vector push_back +100 growth

Resizes about n/100 times; copy cost Θ(n^2); divide by n ⇒ amortized Θ(n) per push.

Binary counter increment

Total bit flips ≤ 2n for n increments ⇒ amortized O(1).

Lower bound theorem

Any comparison-based sort needs at least ⌈log₂(n!)⌉ comparisons = Θ(n log n).

Sorts exempt from lower bound

Counting, Radix, Bucket (use key structure, not just comparisons).

Why radix requires stable sort

LSD radix sort preserves earlier digit order only if the inner sort (counting) is stable.

Insertion sort stability

Stable: equal elements keep their relative order.

Selection sort stability

Not stable: swapping can break relative order of equals.

Best sort for values {0,1,2}

Counting sort: O(n+k)=O(n) since k=3.

Least efficient sort for {0,1,2}

Selection sort: Θ(n^2) even if nearly sorted.

Stack vs Queue input reversal

Stack reverses input (LIFO); Queue models lines/shelf restocking (FIFO).

Stack operations runtimes

Push = amortized O(1); Pop, Top, is_empty = O(1).

Queue operations runtimes

Enqueue = amortized O(1); Dequeue = O(1) with ring buffer or linked list.

Binary search cost when n doubles

log₂(2n) = log₂ n + 1 ⇒ only +1 extra comparison.

Insertion sort best case

Already sorted array; runtime Θ(n).

Pointer storage

Pointer variable lives on the stack; pointee allocated with new lives on the heap.

Pointer operators

(p++) uses then increments; (--p) decrements then uses; (p)++ prints then increments element; ++(p) increments element then prints.

Shallow copy problem

Copies pointer value only ⇒ double delete, aliasing bugs, dangling pointer if one object frees.

Rule of Three/Five

If a class manages resources (e.g., raw pointers), define destructor, copy constructor, copy assignment (and move versions in C++11+).

Insertion sort runtimes

Best: O(n) (already sorted). Worst: O(n^2) (reverse sorted). Average: O(n^2).

Selection sort runtimes

Best: O(n^2). Worst: O(n^2). Average: O(n^2).

Bubble sort runtimes

Best: O(n) (if early exit check). Worst: O(n^2). Average: O(n^2).

Counting sort runtimes

Best/Worst/Average: O(n+k). Linear when k = O(n).

Radix sort runtimes

Best/Worst/Average: O(d·(n+k)). Linear when digit count d and base k are constants.

Bucket sort runtimes

Best: O(n+k) (uniform distribution). Worst: O(n^2) (all elements fall in one bucket). Average: O(n+k).

Binary search runtimes

Best: O(1) (target at middle). Worst: O(log n). Average: O(log n).