Reasonable vs Unreasonable Time

Reasonable (polynomial): n, n², n³, log n -- grows manageably with input size.
Unreasonable (exponential): 2⊃n⊃, n! -- grows so fast that even small inputs become unsolvable.

An exponential algorithm for n=100 produces more steps than atoms in the observable universe.

# Linear: O(n) -- checks each element once
def linear_search(lst, target):
    for item in lst:
        if item == target:
            return True
    return False

# Binary: O(log n) -- much faster on sorted data

{Polynomial examples:}
{Linear: n steps}
{Binary search: log n steps}
{Bubble sort: n^2 steps}

{Exponential:}
{2^n grows too fast for large n}

Why Faster Hardware Barely Helps Exponential Algorithms

10x faster hardware adds only log⊂2⊂(10) ≈ 3 more usable input size for an exponential algorithm. For polynomial algorithms, 10x speedup translates to a meaningful improvement in problem size handled.

Practice Problems