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 |
|---|---|---|
| 10 | 1,024 | about 1 millisecond |
| 20 | 1,048,576 | about 1 second |
| 30 | 1,073,741,824 | about 18 minutes |
| 40 | 1,099,511,627,776 | about 13 days |
| 50 | 1,125,899,906,842,624 | about 36 years |
- 1,024x
- 1.8x
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?
- About 32 seconds: 2 more sources out of 25 adds about 8%
- About 2 minutes: each added source doubles the combinations
- About 35 seconds: work grows with the square of the sources
- About 60 seconds: adding sources doubles the work once
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 adding | Without the item | With the item | Total |
|---|---|---|---|
| nulls | [] | [nulls] | 2 |
| dupes | [], [nulls] | [dupes], [nulls, dupes] | 4 |
| schema | the 4 combinations so far | 4 copies with schema added | 8 |
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.