Intro & Complexity — Big-O

Code

algo find — your first measurement

The last piece is the search itself. Create find.go and find_test.go (see the panel).

LinearFind walks the library from the front and counts every title comparison. That is the whole algorithm: three lines and a counter.

Your first measurement

$ algo gen -n 1000 -seed 42
wrote 1000 items to library.jsonl (seed=42, order=shuffled, dup-rate=0.00)

$ algo find -title "Gubątėva"
found at index 0: Gubątėva — Gąčuku (2020, rating 20)
n = 1000, comparisons = 1

$ algo find -title "Šibąču"
found at index 999: Šibąču — Žąžame (1940, rating 89)
n = 1000, comparisons = 1000

$ algo find -title "Nėra tokio"
not found: "Nėra tokio"
n = 1000, comparisons = 1000

The three cases from step 1, measured: best is 1, worst is 1000, and a miss is 1000 too. A miss is always the worst case — you cannot say something is absent without having looked at everything.

This is what O(n) means

Grow the library tenfold and watch the number:

n=1000     n = 1000,   comparisons = 1000
n=10000    n = 10000,  comparisons = 10000
n=100000   n = 100000, comparisons = 100000

Ten times the data, ten times the work. A straight line. That is exactly what O(n) says, and now you can see it rather than take it on trust.

The test you have to pass

find_test.go checks the answer and the cost:

$ go test -run TestLinearFindCountsAreExact -v .
=== RUN   TestLinearFindCountsAreExact
=== RUN   TestLinearFindCountsAreExact/best_case:_first_item
=== RUN   TestLinearFindCountsAreExact/third_item
=== RUN   TestLinearFindCountsAreExact/worst_case:_last_item
=== RUN   TestLinearFindCountsAreExact/miss:_scans_everything
--- PASS: TestLinearFindCountsAreExact (0.00s)
PASS
ok  	algo	0.417s

Remember this shape — it recurs for the rest of the course. The test demands an exact comparison count, not "roughly that many". In later lessons it will demand "no more than n log n" — and a test like that cannot be fooled by the wrong algorithm, however correct its answers are.

In a real system

So you can see this is not a classroom exercise: transit is a working Vilnius public-transport route planner. It solves the same route two ways — with a naive queue and with a heap — and reports both the time and the operation count. Three different routes:

Query	Queue work (naive ÷ heap)	Time (naive ÷ heap)
cross-city	249×	16.0×
slow-naive	257×	18.9×
worst case	324×	16.4×

Same query, same answer, and the work ratio is 15–20 times larger than the time ratio. The clock is not lying — it is measuring something other than what you think: the naive queue scans an array front to back, and a processor does that kind of reading very cheaply. A hundred million cheap operations take less time than a million expensive ones.

This is exactly why we count operations in this lesson. If you had measured with a clock alone, you would have found a 16× difference where the difference in work is 249×.

A bound is not a prediction

The same program teaches a second lesson. A naive route search over the full-day graph could in theory do 4.28 × 10¹⁰ operations. Measured, it took 558 ms — only 19.6× slower than the good version, not the ~1000× that had been projected.

The bound did not fail because it was wrong. It failed because a bound is a ceiling, not a prediction: the algorithm stops as soon as it has the answer and never looks at the whole graph.

Keep that distinction — between "the most this could cost" and "what it cost" — for the rest of the course. Big-O tells you the first. The counter tells you the second.

find.go CREATE

Create this file in ./

package main

import (
	"flag"
	"fmt"

	"algo/metrics"
)

// LinearFind scans the library from the front and returns the index of the
// first item whose Title matches, or -1. Every title comparison is counted.
//
// This is the O(n) baseline. Every structure in the rest of the course is
// measured against this number.
func LinearFind(items []Item, title string, c *metrics.Counter) int {
	for i := range items {
		c.Hit()
		if items[i].Title == title {
			return i
		}
	}
	return -1
}

func cmdFind(args []string) error {
	fs := flag.NewFlagSet("find", flag.ContinueOnError)
	in := fs.String("in", "library.jsonl", "library file")
	title := fs.String("title", "", "exact title to find")
	if err := fs.Parse(args); err != nil {
		return err
	}
	if *title == "" {
		return fmt.Errorf("-title is required")
	}
	items, err := load(*in)
	if err != nil {
		return err
	}
	var c metrics.Counter
	i := LinearFind(items, *title, &c)
	if i < 0 {
		fmt.Printf("not found: %q\n", *title)
	} else {
		it := items[i]
		fmt.Printf("found at index %d: %s — %s (%d, rating %d)\n",
			i, it.Title, it.Artist, it.Year, it.Rating)
	}
	fmt.Printf("n = %d, comparisons = %d\n", len(items), c.N())
	return nil
}

find_test.go CREATE

Create this file in ./

package main

import (
	"testing"

	"algo/metrics"
)

// lib is a tiny fixed library — small enough to reason about by hand, which is
// the point: you should be able to predict every count below before running it.
func lib() []Item {
	return []Item{
		{ID: 1, Title: "Aidas", Artist: "Vega", Year: 1999, Rating: 70},
		{ID: 2, Title: "Bangos", Artist: "Vega", Year: 2004, Rating: 55},
		{ID: 3, Title: "Ciklas", Artist: "Nova", Year: 2011, Rating: 90},
		{ID: 4, Title: "Dūmai", Artist: "Nova", Year: 1987, Rating: 40},
	}
}

func TestLinearFindLocatesItems(t *testing.T) {
	items := lib()
	for want, it := range items {
		var c metrics.Counter
		if got := LinearFind(items, it.Title, &c); got != want {
			t.Errorf("LinearFind(%q) = %d, want %d", it.Title, got, want)
		}
	}
}

func TestLinearFindMissingReturnsMinusOne(t *testing.T) {
	items := lib()
	var c metrics.Counter
	if got := LinearFind(items, "Nėra tokio", &c); got != -1 {
		t.Errorf("missing title: got %d, want -1", got)
	}
}

// The COUNTS are the specification, not an afterthought. Best case is 1
// comparison, worst case and a miss are both n. If your implementation does
// not produce exactly these numbers it is doing extra work somewhere.
func TestLinearFindCountsAreExact(t *testing.T) {
	items := lib()
	cases := []struct {
		name  string
		title string
		want  int64
	}{
		{"best case: first item", "Aidas", 1},
		{"third item", "Ciklas", 3},
		{"worst case: last item", "Dūmai", 4},
		{"miss: scans everything", "Nėra tokio", 4},
	}
	for _, tc := range cases {
		t.Run(tc.name, func(t *testing.T) {
			var c metrics.Counter
			LinearFind(items, tc.title, &c)
			if c.N() != tc.want {
				t.Errorf("comparisons = %d, want %d", c.N(), tc.want)
			}
		})
	}
}

// Determinism: the same search on the same data must cost the same every time.
// A count that wobbles is not a measurement.
func TestCountIsDeterministic(t *testing.T) {
	items := lib()
	var first int64
	for i := 0; i < 100; i++ {
		var c metrics.Counter
		LinearFind(items, "Dūmai", &c)
		if i == 0 {
			first = c.N()
			continue
		}
		if c.N() != first {
			t.Fatalf("run %d counted %d, first run counted %d", i, c.N(), first)
		}
	}
}