Intro & Complexity — Big-O

Code

The record — and why two fields are bounded

We start with the record type. It looks dull — four fields — but two of them are bounded, and those bounds are a decision, not an accident.

Set the project up:

mkdir algo && cd algo
go mod init algo

go mod init writes go.mod. You will never edit it by hand — Go maintains it for you.

Then item.go (see the panel).

Why `Year` and `Rating` have limits

Title and Artist are strings — they can be anything. Year and Rating cannot: a year is between 1900 and 2030, a rating between 0 and 100.

That looks like a detail. It is not.

The sorting you write in lessons 7 and 8 compares items to each other. That kind of sort works on anything you can order — and the fastest one possible is O(n log n).

Lesson 9's sort compares nothing at all. It is faster — O(n) — but only if you know the range of the values in advance, because it needs one bucket per possible value. 131 years and 101 ratings are easy to bucket. Titles are not.

So these two fields get their limits now, eight lessons before anything needs them. It is the one decision in this lesson you could not change later without regenerating your data.

Gotcha

ID is separate from the position in the slice. When you sort the library in lesson 7 the items move — but the ID stays stuck to its item. Never use an index as an identifier.

item.go CREATE

Create this file in ./

package main

// Item is one record in your library. Every lesson in this course stores,
// searches, sorts or indexes these.
//
// Year and Rating are BOUNDED on purpose — see the constants below.
type Item struct {
	ID     int
	Title  string
	Artist string
	Year   int // MinYear..MaxYear
	Rating int // MinRating..MaxRating
}

// The bounds are part of the data model, not validation trivia.
//
// A comparison sort works on anything you can order. A COUNTING or RADIX sort
// (lesson 9) needs to know the range of the key in advance, so it can allocate
// one bucket per possible value. 131 years and 101 ratings are small enough to
// bucket; a Title is not. That is why those two fields have limits and the
// strings do not.
const (
	MinYear   = 1900
	MaxYear   = 2030
	MinRating = 0
	MaxRating = 100
)

The record — and why two fields are bounded

Why Year and Rating have limits

Why `Year` and `Rating` have limits