Library Call Costs in Practice

Library calls have complexity too

Clean code often hides loops inside library calls. In Python: x in list is O(n) but x in set is O(1) average; list.index, list.remove, list.count and min/max are O(n); list.insert(0, x) and pop(0) are O(n); slicing a[i:j] copies j − i elements; sorted() and list.sort() use Timsort, O(n log n) worst case and very fast on partly sorted data; heapq.heappush is O(log n); len() is O(1). Repeated string concatenation in a loop can be O(n²) because strings are immutable; build a list and ''.join() it. In Java: ArrayList.get is O(1) and add amortised O(1), but remove(0) is O(n); LinkedList.get(i) is O(n); HashMap.get is O(1) average; TreeMap.get is O(log n); String += in loops creates new strings each time, so use StringBuilder; Collections.sort and List.sort are O(n log n). Knowing these costs prevents accidentally quadratic code that looks perfectly innocent.

Accidentally quadratic code and its fixes

Each pair does the same job with very different growth.

# 1. membership test in a list inside a loop: O(n * m)
banned = load_banned_ids()            # list of m ids
clean = [u for u in users if u.id not in banned]
# fix: O(n + m)
banned_set = set(banned)
clean = [u for u in users if u.id not in banned_set]

# 2. string building: can be O(n^2) because each += may copy the whole string
report = ""
for line in lines:
    report += line + "\n"
# fix: O(n)
report = "\n".join(lines) + "\n"

# 3. queue with a list: O(n^2) for n items
queue = list(tasks)
while queue:
    task = queue.pop(0)
# fix: O(n)
from collections import deque
queue = deque(tasks)
while queue:
    task = queue.popleft()

Read the documentation's complexity notes

Python's wiki page on time complexity and the Java collections documentation list the costs of standard operations. A minute there saves hours of debugging a slow endpoint.

त्वरित जाँच: What is the cost of `x in my_list` for a Python list of n elements?

• O(n)
• O(1)
• O(log n)
• O(n log n)