Exponential Time

Some questions ask which combination of items is best: which sources to backfill tonight, which checks fit inside a time budget. Each item is in the combination or out of it, so 1 item gives 2 choices, 2 items give 2 × 2 = 4, and n items give 2ⁿ. Code that tries every combination does O(2ⁿ) work.

checks = ["nulls", "dupes", "schema"]
combos = [[]]
for check in checks:
    with_check = []
    for combo in combos:
        with_check.append(combo + [check])
    combos = combos + with_check
    print(check, "->", len(combos), "combinations")
print(combos)
nulls -> 2 combinations
dupes -> 4 combinations
schema -> 8 combinations
[[], ['nulls'], ['dupes'], ['nulls', 'dupes'], ['schema'], ['nulls', 'schema'], ['dupes', 'schema'], ['nulls', 'dupes', 'schema']]

The list doubled with every item. That is the signature of exponential time: O(n²) quadruples when n doubles, while O(2ⁿ) doubles when n grows by 1.

Items (n)Combinations (2ⁿ)Time at 1 million per second
101,024about 1 millisecond
201,048,576about 1 second
301,073,741,824about 18 minutes
401,099,511,627,776about 13 days
501,125,899,906,842,624about 36 years

Brute force on a backfill window

A backfill window has 60 minutes, and 4 jobs are waiting with known runtimes. The goal is the set of jobs that fills the window as fully as possible without running over. The program builds every combination with the doubling loop, adds up each one's minutes, and keeps the best fit.

jobs = {"orders": 25, "refunds": 20, "clicks": 35, "sessions": 15}
window = 60

combos = [[]]
for name in list(jobs):
    with_name = []
    for combo in combos:
        with_name.append(combo + [name])
    combos = combos + with_name

best = []
best_minutes = 0
for combo in combos:
    minutes = 0
    for name in combo:
        minutes += jobs[name]
    if best_minutes < minutes <= window:
        best = combo
        best_minutes = minutes

print("combinations tried:", len(combos))
print("best fit:", best, best_minutes, "minutes")

Output:

combinations tried: 16
best fit: ['orders', 'clicks'] 60 minutes

Sixteen combinations finish instantly. The same code over 40 jobs would run for days, and nothing in it looks alarming: no deep nesting, no large input. The growth hides in the list that doubles once per job.

A script checks every combination of 25 candidate data sources and takes 30 seconds. A teammate adds 2 more sources. About how long will it take now?

The line that doubles the list

One line in the combination loop does the doubling: combos = combos + with_check. The old list holds every combination without the new item, and with_check holds a copy of each one with the item added, so the new list is twice as long. Drop the old half and write combos = with_check, and every combination that leaves the item out is lost: the count stays at 1 however many items arrive. The table follows the 3 checks from the animation.

After addingWithout the itemWith the itemTotal
nulls[][nulls]2
dupes[], [nulls][dupes], [nulls, dupes]4
schemathe 4 combinations so far4 copies with schema added8

About this lesson

This section is part of the Complexity: Intermediate lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.