One Pass Over the Data
O(n) means linear time: the work grows in step with the input. Twice the elements, twice the steps.
In Go, linear time usually looks like one for loop over a slice or a map. Every algorithm that must at least look at every element — summing, counting, searching an unsorted slice — cannot be faster than O(n).
Linear is a good complexity. Millions of elements are no problem for one pass.
Linear Search
When the slice is not sorted, the only way to find a value is to check the elements one by one, from the start. That is a linear search.
In the worst case — the value is last, or not there at all — the loop visits all n elements. That worst case is what O(n) describes.
Find a value and its position
The loop checks "one", "two", "three" before it reaches "four" — 4 steps for a match at index 3. break stops the loop as soon as the value is found.
Output: Go program and captured output
package main
import "fmt"
func main() {
words := []string{"one", "two", "three", "four", "five"}
steps := 0
for i, w := range words {
steps++
if w == "four" {
fmt.Println("found at index", i, "after", steps, "steps")
break
}
}
}
Visiting Every Element
Many everyday tasks are one pass over the whole slice: add all values, keep the biggest one seen so far, count the elements that pass a test. Each element is touched exactly once, so all of them are O(n).
Doing two or three of these passes in a row is still linear — O(2n) and O(3n) collapse to O(n).
Sum all elements
The loop adds every element to sum. 8 elements, 8 additions — the classic one-pass shape.
Output: Go program and captured output
package main
import "fmt"
func main() {
nums := []int{3, 1, 4, 1, 5, 9, 2, 6}
sum := 0
for _, n := range nums {
sum += n
}
fmt.Println("sum of", len(nums), "elements:", sum)
}
Find the biggest value
max starts as the first element; every other element that is bigger replaces it. After one pass the biggest value, 9, remains.
Output: Go program and captured output
package main
import "fmt"
func main() {
nums := []int{3, 1, 4, 1, 5, 9, 2, 6}
max := nums[0]
for _, n := range nums[1:] {
if n > max {
max = n
}
}
fmt.Println("biggest value:", max)
}
Count the matches
The loop tests every word with len(w) > 3 and counts the hits. Three words are longer than 3 letters.
Output: Go program and captured output
package main
import "fmt"
func main() {
words := []string{"one", "two", "three", "four", "five"}
count := 0
for _, w := range words {
if len(w) > 3 {
count++
}
}
fmt.Println(count, "words are longer than 3 letters")
}