Algorithms and Computation

Lecture W1M2: Introduction to the Analysis of Algorithms

Lucas P. Cordova, Ph.D.
lpcordova@willamette.edu

Willamette University

August 24, 2026

Learning objectives

What you will leave with

By the end of this session, you will be able to:

  1. Distinguish a computational problem from a problem instance, and state what it means for an algorithm to solve a problem.
  2. Explain why induction is the core tool for proving algorithms correct on arbitrarily large inputs.
  3. Justify why we measure efficiency by counting operations as a function of input size instead of timing programs.
  4. Describe the word-RAM model and what it lets us call a constant-time operation.
  5. Start HW0 knowing exactly what is being asked and why.

What is a problem?

The course in one sentence

The goal of this course is to teach you to solve computational problems, and to communicate that your solutions are correct and efficient.

Half of your grade in life as a computer scientist is the second part: convincing another human. Proofs and analysis are how algorithm designers communicate.

A problem is a relation on inputs and outputs

A computational problem is a binary relation from problem inputs to correct outputs. Because listing every correct output for every input is usually impossible, we instead give a verifiable predicate, a property that any correct output must satisfy.

This course studies problems over large, general input spaces: the problem must be stated for inputs of arbitrary size n, not for one fixed situation.

Instance vs general problem

An instance: In this room, right now, is there a pair of students who share a birthday?

The general problem: Given any set of n students, is there a pair with the same birthday?

Two observations:

  • If a birthday is one of 366 days, then for n > 366 the answer is always yes, by the pigeonhole principle.
  • To keep the general problem interesting, assume birthday resolution finer than n (include year, hour, minute).

What is an algorithm?

Algorithms solve problems

An algorithm is a deterministic procedure mapping each input to a single output. An algorithm solves a problem if it returns a correct output for every input of the problem.

Your neighbor’s checkout-line strategy from the activity is a procedure. Whether it solves the fastest-line problem, for every store on every day, is exactly the kind of claim this course teaches you to interrogate.

A first algorithm: birthday matching

Problem: Given n students, return a pair with the same birthday, or None if none exists.

Algorithm (interview method):

  1. Maintain a record of names and birthdays, initially empty.
  2. Interview each student in some order:
    • If the student’s birthday is already in the record, return the pair.
    • Otherwise, add the name and birthday to the record.
  3. If the last student is interviewed without a match, return None.

Simple. But is it correct? And is it fast? Those are always the two questions.

Correctness

Why correctness needs induction

  • An algorithm is a fixed, finite piece of text, but it must work on arbitrarily large inputs.
  • For small inputs you can check cases by hand. For all inputs, the algorithm must loop or recurse, so proofs must handle unbounded repetition.
  • The tool for that is mathematical induction, which is why recursion and induction sit at the heart of computer science.

“I ran it on ten test cases and it worked” is evidence, not proof. Tests can show the presence of bugs, never their absence.

Proof sketch: birthday matching is correct

Induction hypothesis: if the first k students contain a matching pair, the algorithm returns a match before interviewing student k + 1.

  • Base case k = 0: the empty record contains no match, and the algorithm has returned nothing, as required.
  • Inductive step: assume the hypothesis holds for k’. Consider k’ + 1:
    • If the first k’ students contain a match, the algorithm already returned it, by the hypothesis.
    • Otherwise any match among the first k’ + 1 must involve student k’ + 1, and the algorithm checks that student’s birthday directly against the record of the first k’.

Either way the hypothesis holds for k’ + 1, completing the induction.

Efficiency

How fast is an algorithm?

Wall-clock time is a property of the machine, not the algorithm. We want machine-independent analysis:

  • Count fixed-time operations the algorithm performs before returning.
  • Express the count as a function of input size, usually written n. Bigger inputs, more operations.
  • Call an algorithm efficient if its count is bounded by a polynomial in the input size.
  • For some problems, no efficient algorithm is known to exist. That story ends the semester (P vs NP).

Asymptotic notation, first look

We ignore constant factors and lower-order terms and keep the growth rate:

  • \(O(f(n))\) upper bounds, \(\Omega(f(n))\) lower bounds, \(\Theta(f(n))\) tight bounds.

How growth rates feel at \(n = 1000\), at one operation per nanosecond:

Growth Count at \(n = 1000\) Rough time
constant \(\Theta(1)\) 1 1 ns
logarithmic \(\Theta(\log n)\) about 10 10 ns
linear \(\Theta(n)\) 1000 1 microsecond
log-linear \(\Theta(n \log n)\) about 10,000 10 microseconds
quadratic \(\Theta(n^2)\) 1,000,000 1 millisecond
exponential \(2^{\Theta(n)}\) about \(10^{301}\) longer than the universe

O vs Omega vs Theta: the road trip

Think of estimating how long a trip takes:

  • \(O\) Big O, upper bound: “The trip will take no more than 3 hours.”
  • \(\Omega\) Big Omega, lower bound: “The trip will take at least 2 hours.”
  • \(\Theta\) Big Theta, tight bound: “The trip will take between 2 and 3 hours.”

For algorithms:

  • \(O(n^2)\): the work grows no faster than roughly \(n^2\).
  • \(\Omega(n^2)\): the work grows at least as fast as roughly \(n^2\).
  • \(\Theta(n^2)\): the work grows at the same general rate as \(n^2\).

A useful memory aid:

\[\boxed{O = \text{ceiling}, \quad \Omega = \text{floor}, \quad \Theta = \text{both}}\]

Model of computation

What counts as one operation?

Counting operations only means something if we agree on what the machine can do in constant time. Our model is the word-RAM:

  • Machine word: a block of w bits.
  • Memory: an addressable sequence of machine words; given an address, read or write one word in O(1).
  • Processor: constant-time operations on O(1) words at a time: integer arithmetic (+, -, *, //, %), comparisons and logic, bitwise operations.
  • Addresses must fit in a word, so \(w \geq \log_2\) of the memory size: 32-bit words address about 4 GB; 64-bit words about 16 exabytes.

Python is a much fancier model, but it is implemented on top of a word-RAM, and we will keep track of what its conveniences really cost.

Data structures, a preview

A data structure is a way to store non-constant data supporting a set of operations; the set of operations is called its interface.

Two interfaces organize the first third of the course:

  • Sequence: extrinsic order (first, last, i-th item).
  • Set: intrinsic order (queries by key).

Example: a static array supports build in \(\Theta(n)\) and get_at / set_at in \(\Theta(1)\). Different structures implement the same interface with very different performance, and that difference is the whole game.

Birthday matching, in code

def birthday_match(students):
    """students: tuple of (name, bday) tuples.
    Returns a matching pair of names, or None."""
    n = len(students)                       # O(1)
    record = StaticArray(n)                 # O(n)
    for k in range(n):                      # n rounds
        (name1, bday1) = students[k]        # O(1)
        for i in range(k):                  # k rounds
            (name2, bday2) = record.get_at(i)   # O(1)
            if bday1 == bday2:              # O(1)
                return (name1, name2)       # O(1)
        record.set_at(k, (name1, bday1))    # O(1)
    return None                             # O(1)

How fast is it?

Outer loop runs \(n\) times; the inner loop runs \(k\) times on round \(k\):

\[O(n) + \sum_{k=0}^{n-1}\left(O(1) + k \cdot O(1)\right) = O(n^2)\]

  • Quadratic is polynomial, so this is efficient by our definition.
  • But interviewing 1000 students takes about a million comparisons.
  • Better idea: store the record in a structure with faster lookups. That is exactly where hashing (week 3) takes us, and why data structures come first.

How to solve an algorithms problem

Two moves, all semester:

  1. Reduce to a problem you already know how to solve, then use a known data structure or algorithm.
  2. Design your own recursive algorithm: brute force, decrease and conquer, divide and conquer, greedy, dynamic programming.

The course builds your toolbox in that order: data structures and sorting, then graphs and shortest paths, then design paradigms, then the limits of computation. Keep a running inventory; by the final you will pattern-match problems to tools on sight.

HW0: assigned today

What HW0 is and why

HW0 is assigned today, due Monday, August 31 at 9:59 PM, via Canvas.

It is an individual prerequisite self-check, completed without collaboration or outside help. It is scored for feedback but does not count toward your final grade: it is a diagnostic that tells both of us where your background stands, and a chance to practice LaTeX before the graded work begins.

Written portions must be prepared in LaTeX (a template is provided in Canvas). This applies to all homework and exams in the course; the Getting Started with LaTeX guide on the course Resources page has you covered.

If HW0 feels rough, that is a signal to visit student hours or our TA’s help hours, this week, not week 6.

What is on it

Six short problems, all prerequisite material:

  1. Set operations: intersection, union, difference on two small finite sets.
  2. Expectation: expected values from coin flips and dice, including linearity of expectation.
  3. Modular arithmetic: congruence checks mod 2, 3, and 4.
  4. Induction proof: a closed form for a factorial summation.
  5. Graph induction proof: an acyclic undirected graph with |E| = |V| - 1 is connected.
  6. Python: write count_long_subarrays(A), counting the longest strictly decreasing consecutive runs in a tuple.

The coding problem, concretely

count_long_subarrays(A) returns how many decreasing subarrays of A achieve the maximum length.

Example: for A = (6, 4, 2, 5, 9, 7, 3, 8, 1) the longest decreasing subarrays have length 3, and there are two of them: (6, 4, 2) and (9, 7, 3). So return 2.

  • A subarray is consecutive; a subsequence is not. Read the definitions carefully.
  • Templates and test cases are in Canvas. Passing the provided tests is necessary, not sufficient: we grade correctness on inputs you have not seen.
  • One clean pass over the array suffices. Ask yourself: what state do you carry, and what is your loop invariant?

Before Wednesday

  1. Start HW0 tonight. The proofs benefit from a day of thinking; do not start Sunday.
  2. Read the syllabus on Canvas; bring questions Wednesday.
  3. Supplemental reading for Wednesday (highly recommended): CLRS Chapter 10 and Section 16.4, in your own copy or online through Canvas/Perusall.
  4. Wednesday: data structures and sequences, where interfaces meet implementations and we make “O(1) per operation” earn its keep.

Welcome to CS 351. It is going to be a great semester.

References

Sources

  1. Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, 4th edition, MIT Press. Chapters 1 to 3.
  2. CS 351 Syllabus and schedule, Fall 2026: Canvas.
  3. HW0 assignment, templates, and test cases: Canvas.