Algorithms & Complexity: A Senior-Level Overview

Grade 12 · Technology · Study Guide

A college-prep deep dive into algorithm design paradigms, Big O analysis, and the theoretical limits of computation.

An algorithm is a finite, deterministic sequence of steps that solves a well-defined problem. Analyzing algorithms means asking two questions: how fast does it run (time complexity) and how much memory does it consume (space complexity)? Big O notation answers both by expressing growth rates relative to input size n, ignoring constant factors and lower-order terms. O(1) is constant, O(log n) is logarithmic, O(n) is linear, O(n log n) is linearithmic, O(n²) is quadratic, and O(2ⁿ) is exponential.

Four major algorithm design paradigms dominate computer science. Divide and conquer splits a problem into independent subproblems, solves them recursively, and merges results — merge sort and binary search are canonical examples. Dynamic programming (DP) handles problems with overlapping subproblems and optimal substructure by storing partial results in a table (tabulation) or cache (memoization), transforming exponential naive solutions into polynomial ones. Greedy algorithms make the locally optimal choice at every step; they work correctly for problems with the greedy-choice property, such as Dijkstra's shortest path and Huffman coding. Backtracking exhaustively explores a solution space by building candidates incrementally and abandoning a branch as soon as a constraint is violated.

Complexity classes formalize the inherent difficulty of problems, not just the algorithms that solve them. The class P contains problems solvable in polynomial time; NP contains problems whose solutions can be verified in polynomial time. Whether P equals NP is the most famous unsolved problem in computer science. NP-complete problems, like the traveling salesman and Boolean satisfiability, are the hardest problems in NP — a polynomial-time algorithm for any one of them would solve all of them.

Understanding complexity guides real engineering decisions. Choosing a hash table (O(1) average lookup) over a sorted array (O(log n) binary search) might seem obvious, but hash tables consume more memory and have poor worst-case behavior without a strong hash function. Recognizing that a nested loop yields O(n²) helps engineers spot performance bottlenecks before they reach production.

Key terms

Big O Notation: Mathematical notation describing an algorithm's worst-case growth rate; O(f(n)) means execution time or space grows no faster than a constant multiple of f(n).
Divide and Conquer: A design paradigm that recursively breaks a problem into independent subproblems, solves each, then merges results; used in merge sort and binary search.
Dynamic Programming: An optimization technique for problems with overlapping subproblems and optimal substructure; stores intermediate results to eliminate redundant computation.
NP-Complete: A class of decision problems that are both in NP (solutions verifiable in polynomial time) and NP-hard (at least as hard as every problem in NP).
Greedy Algorithm: An approach that selects the locally optimal choice at each step; correct when the problem has the greedy-choice property and optimal substructure.
Amortized Analysis: A method of averaging the cost of operations over a sequence to show that expensive individual operations are rare, as in dynamic array resizing.

Flashcards

O(log n): Logarithmic time complexity; the algorithm halves the search space each step, as in binary search on a sorted array.
Memoization: A top-down DP technique that caches the return values of recursive calls so identical inputs are never computed twice.
Tabulation: A bottom-up DP technique that fills a table iteratively from base cases to the final answer, avoiding recursion overhead.
Greedy-Choice Property: The guarantee that a globally optimal solution can be reached by making locally optimal choices at each step.
P vs NP: The open question of whether every problem whose solution can be verified quickly (NP) can also be solved quickly (P).
Backtracking: An algorithm that builds solution candidates incrementally and abandons a branch as soon as it violates a constraint.
Space Complexity: The amount of memory an algorithm requires relative to input size, expressed in Big O notation alongside time complexity.
Recurrence Relation: An equation that expresses the runtime of a recursive algorithm in terms of the runtime of smaller inputs; solved with the Master Theorem.
Master Theorem: A formula for solving recurrences of the form T(n) = aT(n/b) + f(n), commonly used to analyze divide-and-conquer algorithms.
Optimal Substructure: A property of a problem where the optimal solution contains optimal solutions to its subproblems; required for both DP and greedy approaches.
Reduction: Transforming one problem into another to show that solving the second solves the first; used to prove NP-hardness.
Polynomial Time: Runtime expressible as O(nᵏ) for some constant k; considered efficiently solvable for practical purposes.

Questions

Which time complexity class describes an algorithm whose runtime doubles with every additional input element?
1. O(n)
2. O(n²)
3. O(2ⁿ)
4. O(log n)
Show answer
Answer: O(2ⁿ)
O(2ⁿ) means the runtime doubles with each additional element; naive recursive Fibonacci is a classic example.
Dynamic programming is only applicable to problems where subproblems are completely independent of one another.
Show answer
Answer: False
DP specifically handles problems with overlapping subproblems — if subproblems were independent, plain recursion or divide and conquer would suffice.
Merge sort achieves its O(n log n) time complexity by using which algorithm design paradigm?
1. Greedy
2. Dynamic Programming
3. Backtracking
4. Divide and Conquer
Show answer
Answer: Divide and Conquer
Merge sort splits the array in half recursively (divide), sorts each half, then merges in O(n) per level across O(log n) levels.
The complexity class containing all problems solvable in polynomial time is called ______.
Show answer
Answer: P
P (polynomial time) is the complexity class for problems solvable efficiently; NP is for problems whose solutions are verifiable in polynomial time.
A nested loop where the outer runs n times and the inner runs n times gives which worst-case time complexity?
1. O(n)
2. O(n log n)
3. O(n²)
4. O(2ⁿ)
Show answer
Answer: O(n²)
Two nested loops each iterating n times perform n × n = n² total operations, giving O(n²) quadratic complexity.

Get a personalized course on Algorithms & Complexity built around your child.