Time Complexity Optimization (attack the dominant term)

Time complexity optimization targets the dominant term—replace O(n²) with O(n log n) sort, O(n) hash, or O(log n) binary search. Prove the new bound dominates all steps.

Why this shows up in the real world

Search moved from linear scan to inverted indexes at web scale. Routing tables use tries for O(prefix) lookup.

Core idea (explained for students)

Identify nested loops or repeated sorts; introduce hashing or monotonic structures to remove an inner linear factor.

Try this in Python

def two_sum_sorted(a: list[int], t: int) -> bool:
    a.sort()
    i, j = 0, len(a) - 1
    while i < j:
        s = a[i] + a[j]
        if s == t:
            return True
        if s < t:
            i += 1
        else:
            j -= 1
    return False


print(two_sum_sorted([3, 1, 4, 5], 9))

Common mistakes

• Hidden log factors from heaps used inside loops multiplying incorrectly.
• Amortized structures mis-summed across phases.

Key takeaways

• After change, write T(n) = ... as a short recurrence or sum of terms.
• Keep worst-case examples that used to timeout as regression tests.