Time Complexity
Time complexity is a measure of how the running time of an algorithm changes as the size of its input grows. Rather than measuring actual seconds, which de...
Measuring How Running Time Grows with Input Size
Time complexity is a measure of how the running time of an algorithm changes as the size of its input grows. Rather than measuring actual seconds, which depend on hardware, compiler, and operating conditions, time complexity counts the number of fundamental operations the algorithm performs as a function of the input size n.
The most common time complexities, from fastest to slowest, are O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n^2) quadratic, O(n^3) cubic, O(2^n) exponential, and O(n!) factorial.
An O(1) operation completes in a fixed number of steps regardless of input size. Accessing an element of an array by index is O(1): the memory address is computed directly as base address plus index times element size, with no iteration needed.
O(log n) algorithms repeatedly halve the problem. Binary search in a sorted array of n elements takes at most log2(n) steps. For one billion elements, that is only thirty comparisons.
O(n) algorithms scan all elements once. Finding the maximum value in an unsorted array requires looking at every element, giving O(n) time.
O(n log n) is the complexity of the best general-purpose sorting algorithms: merge sort, heap sort, and the average case of quicksort. This is also the theoretical lower bound for comparison-based sorting.
O(n^2) algorithms often involve nested loops where both iterate over the input. Bubble sort and insertion sort are O(n^2) in the worst case. These are acceptable for small inputs but impractical for large ones.
To analyze an algorithm, count how many times the most expensive operation runs in terms of n. For a single loop from 0 to n, the count is n, giving O(n). For nested loops each running from 0 to n, the count is n times n, giving O(n^2). Drop constant factors and lower-order terms: 5n^2 + 3n + 7 is O(n^2).
Worked example: given an array of n integers, does it contain a duplicate? A brute-force approach uses two nested loops to compare every pair, giving O(n^2) time. Sorting the array first and checking adjacent elements gives O(n log n). Using a hash set to track seen values gives O(n) time with O(n) space. The right trade-off depends on memory constraints.
Interview tip: always state the time complexity of your solution before the interviewer asks. Follow it with the space complexity. This signals that you think about efficiency as a natural part of your problem-solving process.