DSA Foundations

A Simple Algorithm

You need the hottest SKU in a warehouse snapshot of n = 10⁷ readings. Sorting the whole list works, but burns Θ(n log n) before you can answer. A single scan keeping a running maximum finishes in one pass and teaches the habits every harder algorithm still uses.

An is a finite recipe with defined input and output. Here we practice stating a , counting cost in the , and noticing when recursion hides .

What happens first?

Fix I/O

Empty list? Return null, throw, or disallow?

Single scan

Seed from the first element; update on each larger value.

max_val is the max of the prefix seen so far.

Cost claim

Θ(n) time, Θ(1) extra space in the RAM model.

What actually happens

Naive idea: sort descending and take the first element. Correct for a non-empty list, but you pay Θ(n log n) and usually Θ(n) extra space (or mutate order you may still need).

Break: at n = 10⁷, sorting is unnecessary work when the question only asks for one extreme value. You must still read every element once in the comparison model if any of them could be the unique max.

Better idea: keep a running candidate. After each step the candidate is the maximum of the prefix examined so far. That plus (the remaining unexamined suffix shrinks) is the whole proof.

Invariant

After each iteration, max_val equals the maximum of all elements examined so far. When the loop ends, that set is the full array, so the answer is global.

How to choose a first algorithm

1. Is one pass enough? Extremes, sums, and many filters need only a linear scan. Sort only when order itself is required.

2. Can you name the invariant in one sentence? If not, the steps are still unclear. Write the claim before the loop body.

3. Will recursion recompute the same states? If yes, prefer iteration or memoization (see Fibonacci below) instead of naive recursion.

Quantitative check

n = 10⁷ elements: one scan is ~10⁷ comparisons. Sorting is about 10⁷ × 23 ≈ 2.3 × 10⁸ comparisons before you even read the first result. The scan wins whenever the only question is “what is the max?”

Five properties of a good algorithm

Input

Clearly defined data (and constraints on size / shape).

Output

A precise result for every valid input.

Definiteness

Each step is unambiguous: no “somehow sort it.”

Finiteness

It must stop after a finite number of steps.

Effectiveness

Steps are basic enough to carry out (in code or by hand).

Worked example: find the maximum

Problem: given a non-empty list of numbers, return the largest value. This is the “hello world” of scanning algorithms, and a clean place to practice the solve loop.

Steps (pseudocode)

If the list is empty → decide: error or sentinel (clarify!). Otherwise continue.
Set max_val = first element.
For each remaining element: if larger, update max_val.
Return max_val.

Dry run: [3, 7, 2, 9, 5]

Seen so far	Candidate	max_val
[3]	(start)	3
[3,7]	7 > 3	7
…+2	2 < 7	7
…+9	9 > 7	9
…+5	5 < 9	9

Answer: 9. Every element examined exactly once.

Python

python

def find_max(numbers):
    if not numbers:
        return None  # or raise ValueError: say which you choose

    max_val = numbers[0]
    for num in numbers[1:]:
        if num > max_val:
            max_val = num
    return max_val

# Tests worth naming out loud
assert find_max([3, 7, 2, 9, 5]) == 9
assert find_max([-4, -1, -9]) == -1
assert find_max([42]) == 42
assert find_max([]) is None

Java

java

class Algorithm {
    static Integer findMax(int[] numbers) {
        if (numbers == null || numbers.length == 0) {
            return null; // or throw IllegalArgumentException
        }
        int maxVal = numbers[0];
        for (int i = 1; i < numbers.length; i++) {
            if (numbers[i] > maxVal) {
                maxVal = numbers[i];
            }
        }
        return maxVal;
    }
}

Loop invariant (how to prove correctness)

A is a claim that stays true before the loop, after every iteration, and implies the answer when the loop ends.

After each iteration, max_val equals the maximum of all elements examined so far.

Initialization: before the loop, “so far” is just index 0.
Maintenance: comparing and updating keeps the claim true for one more element.
Termination: every element has been examined → max_val is the global maximum.

Complexity for find_max

Time: O(n)

We look at each of the n elements a constant number of times. No nested loops. You cannot do better in the comparison model if every element might be the unique maximum (you must read it).

Space: O(1)

Only a few scalars (max_val, loop index). Extra space does not grow with n. Sorting first would be O(n log n) time and usually unnecessary.

More notation: Time complexity intro.

Second mini-example: reverse an array in place

Same muscles: clarify (mutate vs new array?), state invariant, give complexity.

python

def reverse_inplace(a):
    i, j = 0, len(a) - 1
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1
    return a
# Invariant: a[0..i) and a(j..n) are already in final reversed positions.
# Time O(n), space O(1). This is also a two-pointers pattern.

Pattern catalog: Problem-solving patterns.

Edge cases to check

Empty input / null
Single element
All equal
Negatives / zeros
Already sorted / reverse sorted
Integer overflow (Java int vs long)

What “cost” counts

Analysis usually uses the : comparisons and assignments are O(1), random access is O(1). That ignores cache and branches: good for ranking algorithms, approximate for micro-benchmarks.

Simple rule of thumb for explaining the solution

Clarify: “Can the list be empty? Should I return null or throw?”
Brute: “Scan once keeping a running max: that is already optimal.”
Invariant: “max_val is the max of the prefix seen so far.”
Complexity: “O(n) time, O(1) extra space.”
Tests: empty, single, all equal, negatives.

Fibonacci: iteration vs recursion

What is it?

Each number is the sum of the two before it, usually starting with 0 and 1:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Classic follow-up: naive recursion is exponential; iteration (or memoization) is linear because of .

Iterative (loops)

Build upward. No repeated work. Preferred default unless the task specifically asks for recursion.

Python

python

def fib_iterative(n):
    if n < 0:
        raise ValueError("n must be >= 0")
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b
# Time O(n), space O(1)

Java

java

static long fibIterative(int n) {
    if (n < 0) throw new IllegalArgumentException();
    if (n <= 1) return n;
    long a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        long next = a + b;
        a = b;
        b = next;
    }
    return b;
}

Pros: O(n) time, O(1) memory

Naive recursive

Elegant, but the call tree recomputes the same subproblems many times → exponential.

Python

python

def fib_recursive(n):
    if n <= 1:
        return n
    return fib_recursive(n - 1) + fib_recursive(n - 2)
# Time ~O(φⁿ), space O(n) call stack
# Fix: memoize or bottom-up DP

Java

java

static int fibRecursive(int n) {
    if (n <= 1) return n;
    return fibRecursive(n - 1) + fibRecursive(n - 2);
}

Cons: ~O(2ⁿ) time, deep call stack

Memoized recursion (bridge to DP)

Cache each fib(k) the first time you compute it. Then you only fill O(n) states.

python

from functools import lru_cache

@lru_cache(None)
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)
# Time O(n), space O(n) for the cache + stack

Deeper: Memoization.

Interactive visualizer

Loading visualizer…

Key insight: loops vs recursion

Recursion maps cleanly to tree-shaped problems (divide-and-conquer, DFS). For linear sequences like Fibonacci, a loop (or memoized DP) is usually clearer and safer on stack limits.

Always volunteer the complexity of both approaches, and name memoization/DP as the fix for .

Exercises

Write the for in-place reverse with pointers i and j. What must remain true after each swap?
At n = 40, estimate why naive recursive Fibonacci fails a one-second budget while the iterative version finishes instantly. What changes at n = 10⁵ for the iterative version if you use 64-bit integers?
Give a counterexample input where sorting-then-take-first and a running-max scan disagree if you forget to handle an empty list the same way.

Primary sources

Cormen et al., Introduction to Algorithms (CLRS): loop invariants (Chapter 2) and Fibonacci as a recurrence example.
Dijkstra, “On the Cruelty of Really Teaching Computing Science”: clarity of algorithmic reasoning.
Python functools.lru_cache documentation: memoizing pure recursive functions.

Takeaway

An algorithm is a finite, clear recipe with defined I/O. Prove it with an invariant, measure it with Big-O, and name edge cases before you trust the code. Fibonacci shows the same discipline when recursion hides overlapping work.