Linear time complexity describes work that grows in proportion to input size. In big O notation, it is written O(n): processing twice as many items takes roughly twice as long. section 4.1.2
A single loop over a list or other sequence is usually O(n). Several fixed passes remain linear: they make the line steeper but do not change its overall growth rate. section 4.1.2
Recognize linear work in familiar Python tasks:
- Printing or summing every item in a sequence. section 4.1.2
- Running multiple fixed loops over the same sequence. section 4.1.2
- Iterating through a dictionary or set; direct access and membership checks behave differently and can be constant time. section 4.2.1
- Using lists when membership checks or insertion at arbitrary positions may become slower as the list grows. section 4.2.2
A simple linear pass
for name in names:\n print(name)\n\nThe loop visits each name once, so its running time grows with the number of names. section 4.1.2
def has_duplicates(sequence):
for index1, item1 in enumerate(sequence): #1
for index2, item2 in enumerate(sequence): #2
if item1 == item2 and index1 != index2: #3
return True
return False
Compare a single linear pass with nested loops, where work can grow faster as the input expands. section 4.1.2
