Overview
Time and space complexity are fundamental tools for analyzing algorithm efficiency. They describe how the resources required by an algorithm change as the size of its input increases. Instead of measuring only one execution on one computer, complexity analysis focuses on the growth of computational work and memory requirements.
Input Size
Input size is commonly represented by n. Depending on the problem, n may represent the number of array elements, characters in a string, vertices in a graph, edges in a graph, or records in a dataset. Some problems require multiple size variables, such as V for graph vertices and E for graph edges.
Time Complexity
Time complexity describes how the number of computational operations grows with input size. A theoretical analysis often counts comparisons, assignments, arithmetic operations, or loop iterations. It does not necessarily represent the exact number of processor cycles or seconds.
Space Complexity
Space complexity describes the memory requirements of an algorithm as input size changes. It can include memory used for temporary data structures, variables, recursion, and other additional storage. It is important to distinguish total space from auxiliary space.
Auxiliary Space
Auxiliary space is the additional memory used by an algorithm beyond the memory occupied by its input. For example, an iterative array traversal may require O(1) auxiliary space, while copying the array into another array requires O(n) auxiliary space.
Constant Complexity
An operation has constant complexity when its cost does not grow with input size under the computational model. Reading an element at a known index in a conventional array is commonly treated as O(1).
Linear Complexity
Linear complexity occurs when computational work grows proportionally to input size. Traversing every element of an array once is a standard O(n) example.
Quadratic Complexity
Quadratic complexity occurs when the work grows proportionally to the square of the input size. A typical example is a pair of nested loops where both loops execute approximately n times.
Logarithmic Complexity
Logarithmic complexity commonly occurs when an algorithm repeatedly reduces the remaining problem size by a constant factor, such as dividing a sorted search interval in half during binary search.
Linearithmic Complexity
O(n log n) complexity often appears in efficient comparison-based sorting algorithms, including merge sort and average-case quicksort.
Recursive Complexity
Recursive algorithms require analysis of their repeated calls and the work performed at each call. Recurrence relations are frequently used to describe these requirements.
Asymptotic Notation
Big O, Big Omega, and Big Theta notation describe upper, lower, and tight asymptotic bounds. They provide a mathematical language for discussing how resource requirements grow.
Multiple Parameters
Some algorithms depend on more than one input dimension. For example, graph algorithms may be analyzed using both the number of vertices V and edges E. Replacing both with one variable can hide important performance characteristics.