Loading
Loading
Complexity Analysis
The three growth rates you will meet most often, and what kind of code produces each.
By the end of this chapter
The work does not grow with the input. Reading an array element by index, pushing onto a stack, looking up a hash key: all constant.
def first_and_last(nums): # Two reads, regardless of how long nums is. return nums[0], nums[-1]You touch each element a bounded number of times. One pass is linear; three passes are also linear, because 3n is O(n).
def total(nums): running = 0 for value in nums: # exactly n iterations running += value return runningEach step discards a fixed fraction of what remains. Halving is the usual case, and how many times you can halve n before reaching one is, by definition, log₂ n.
n = 1,000,0001,000,000step 0500,000step 1250,000step 2…each step halves the remainder1step 2020 stepsTwenty steps for a million items. Forty for a trillion. This is why binary search feels almost free, and why doubling your data barely changes the cost.
def count_halvings(n): steps = 0 while n > 1: n //= 2 # discard half of what remains steps += 1 return steps # approximately log2(n)A logarithmic amount of work done once per element, or a linear amount done at each of log n levels. Comparison sorts land here, and so does anything that sorts first and then scans. Practically speaking, O(n log n) is close enough to linear that it is rarely the bottleneck.
def suspicious(nums): for value in nums: # n iterations if value in nums: # each 'in' scans the whole list: O(n) passOne visible loop, quadratic cost. The membership test hides a second traversal. This is why complexity has to be read in terms of operations performed, not loops written.
Quick quiz
Sign in to keep a note here. It is free, and nobody else can see it.
Sign inWhat this chapter was for:
Before moving on: take the quiz above.