Common Complexity Classes

Math for CS · Axiom Academy

LESSON Common Complexity Classes A tour of the growth rates that appear throughout computer science Algorithms fall into well-known complexity classes. Understanding these classes lets you instantly judge whether an algorithm is efficient or hopelessly slow. Growth rate ordering (slowest to fastest): Here is what these numbers actually look like at different scales: The jump from polynomial to exponential is the difference between "takes a second" and "takes longer than the age of the universe." The operation takes the same amount of time regardless of input size. Hash table lookup (average case) Arithmetic on fixed-size integers Each step eliminates a constant fraction of the remaining work. Extremely fast even for huge inputs. Binary search: Halve the search space each step. steps for a billion elements. Balanced BST operations (search, insert, delete) Finding an element in a sorted array Why logarithms appear: Any process that halves the input each step takes steps to reduce to 1. This is why balanced trees have height . Process each element once. The best you can do if you must read the entire input. Finding min/max of an unsorted array Counting occurrences of a value Single-pass algorithms (e.g., Kadane's for max subarray) The "sweet spot" for comparison-based sorting and many divide-and-conquer algorithms. Merge sort: Divide in half ( levels), merge at each level. Heap sort: Build heap + extract-min operations. Quicksort: average, worst case.

This is the written version of the interactive lesson above. See the full Math for CS course.