Algorithms big picture (correctness & complexity)

Algorithms are step-by-step procedures that always finish and map inputs to outputs. In interviews you defend correctness, termination, and resource bounds (time and space) as a package—not just working code.

Why this shows up in the real world

Maps and navigation use shortest-path and reachability algorithms at planetary scale. Compilers chain graph and string algorithms so your source becomes fast machine code.

Core idea (explained for students)

Model problems as state + transitions (loops, recursion, data-structure ops). Express cost with big-O: count nested loops, depth, and how often the most expensive line runs as n grows.

Try this in Python

def linear_sum(a: list[int]) -> int:
    total = 0
    for x in a:
        total += x
    return total


print(linear_sum([1, 2, 3, 4]))

Common mistakes

• Declaring O(n) when a hidden sort makes it O(n log n).
• Ignoring worst case because random tests feel fast.

Key takeaways

• Write the loop invariant or recurrence before optimizing.
• Compare algorithms by constraints (read-only array, online stream, bounded integers).