A description of how the work (time complexity) or memory (space complexity) an algorithm needs grows with the number of data items n. It is written in Big-O notation, such as O(n), O(n log n) or O(n²), dropping constant factors and lower-order terms.
Japanese name: 計算量
Time complexity (Big-O notation) appears in 2 practice questions across 1 topic, including Data Structures and Algorithms.
O(f(n)) means that for sufficiently large n the work stays within a constant multiple of f(n). An algorithm that makes 3n² + 5n + 2 comparisons is written O(n²), because the n² term dominates as n grows. Common classes, in increasing order, are O(1) (constant), O(log n) (binary search), O(n) (linear search), O(n log n) (merge sort, heapsort), O(n²) (bubble sort, selection sort) and O(2ⁿ) (naive exhaustive search). For n = 1000, log₂ n is about 10, n log₂ n about 10,000 and n² one million, so for large data the difference in complexity is decisive.
The same algorithm can do different amounts of work depending on the input. Insertion sort makes n−1 comparisons, O(n), on sorted data, but n(n−1)/2, O(n²), on reversed data. Quicksort is O(n log n) on average but O(n²) in the worst case, depending on the pivot choice and the data. Systems that need a bound on response time care about the worst case, while estimates of total throughput use the average case. When an occasional expensive step averages out to a constant over many operations, as with appending to a dynamic array, the cost is described as amortized O(1).
Because Big-O notation ignores constant factors, two O(n) algorithms can differ greatly in real speed. On modern computers, main memory is nearly 100 times slower than the L1 cache, so reading an array in order is many times faster than walking a linked list. For small n, a simple algorithm with a worse complexity can also be faster, which is why practical sort implementations use insertion sort for short ranges. When improving performance, first check that no algorithm with an unnecessarily high complexity is being used, then measure and refine details such as memory access patterns.
Answer: C. O(n²)
The number of pairs compared is (n−1) + (n−2) + … + 1 = n(n−1)/2: 45 for n = 10 and 499,500 for n = 1000. Big-O notation only describes how the count grows as n gets large, so the factor of 1/2 and the lower-order term are dropped, giving O(n²). Doubling n roughly quadruples the count. O(n) is the complexity of looking at each element once, and O(n log n) is that of algorithms such as merge sort that repeatedly split the data in half.
Answer: B. 8 seconds
With O(n²), the running time is proportional to the square of the data size, so four times the data takes 4² = 16 times as long: 0.5 s × 16 = 8 s. 2 seconds would be the result for O(n), which is proportional to the data size, and 32 seconds for O(n³), which grows with the cube (4³ = 64 times). In practice it can be even slower, for example once the data no longer fits in the cache.
Changing the base only changes the value by a constant factor (log₂ n = log₁₀ n ÷ log₁₀ 2), so Big-O notation usually omits it. For algorithms that halve the data each step, such as binary search, the actual count is close to log₂ n.
Time complexity is how the work (running time) grows, and space complexity is how the required memory grows. Both are compared together: merge sort is O(n log n) in time with O(n) working space, while heapsort is O(n log n) in time with O(1) space.
Big-O notation only describes how the count grows as n gets large, so the factor of 1/2 and the lower-order term are dropped, giving O(n²).
For an array of n elements, what is the time complexity of …As an Amazon Associate I earn from qualifying purchases.
Array Binary heap Binary search Binary search tree Breadth-first search Depth-first search Dijkstra's algorithm Dynamic programming Greedy algorithm Hash table