Algorithm Complexity with Go - Part 1

Understanding algorithm complexity is essential for developing efficient software solutions. One key aspect of algorithm complexity is ordering growth types, which describe how the runtime of an algorithm scales with the size of the input.

In this series of articles, we’ll explore several ordering growth types , ranging from constant time to exponential time, and discuss their implications for algorithm design and performance.

Constant time complexity

Imagine you have a super speedy delivery service that guarantees your package arrives in the same amount of time, no matter the distance, or your old laptop that infinitely opens as much as Paint and Adobe Photoshop. That’s constant time complexity in action!

Constant time complexity means that the time taken to execute an operation remains constant regardless of the input size.

I’m going to show you this hackneyed example with accessing array element (boring), but with Go benchmarks to give you visualization and make it clear:

func accessElement(arr []int, index int) int {
    return arr[index]
}

Here no matter the size of the array, retrieving an element by index takes the same amount of time.

Let’s prove it in practice by running benchmarks with arrays of 10, 1000, 100000, 100000000 items in length.

package main

import (
    "testing"
)

func accessElement(arr []int, index int) int {
    return arr[index]
}

func BenchmarkAccessElement10(b *testing.B) {
    arr := make([]int, 10) // Array size of 10
    for i := 0; i < len(arr); i++ {
        arr[i] = i
    }
    index := 5 // Fixed index for the array of size 10

    b.ResetTimer() // Isolate all code above
    for i := 0; i < b.N; i++ {
        _ = accessElement(arr, index)
    }
}

func BenchmarkAccessElement1000(b *testing.B) {
    arr := make([]int, 1000) // Array size of 1000
    for i := 0; i < len(arr); i++ {
        arr[i] = i
    }
    index := 500 // Fixed index for the array of size 1000

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        _ = accessElement(arr, index)
    }
}

func BenchmarkAccessElement100000(b *testing.B) {
    arr := make([]int, 100000) // Array size of 100000
    for i := 0; i < len(arr); i++ {
        arr[i] = i
    }
    index := 50000 // Fixed index for the array of size 100000

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        _ = accessElement(arr, index)
    }
}

func BenchmarkAccessElement100000000(b *testing.B) {
    arr := make([]int, 100000000) // Array size of 100000000
    for i := 0; i < len(arr); i++ {
        arr[i] = i
    }
    index := 5000000 // Fixed index for the array of size 100000000

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        _ = accessElement(arr, index)
    }
}

go test -bench .

goos: darwin
goarch: amd64
pkg: algorithms/complexity
cpu: Intel(R) Core(TM) i5-7360U CPU @ 2.30GHz
BenchmarkAccessElement10
BenchmarkAccessElement10-4 1000000000 0.6557 ns/op
BenchmarkAccessElement1000
BenchmarkAccessElement1000-4 1000000000 0.6056 ns/op
BenchmarkAccessElement100000
BenchmarkAccessElement100000-4 1000000000 0.6613 ns/op
BenchmarkAccessElement100000000
BenchmarkAccessElement100000000-4 1000000000 0.6689 ns/op
PASS

Nice! Around 0.6 to 0.7 nanoseconds per operation — execution time remains unchanged even as the array size increases.

Why does it take the same time?

Because the operation is pretty simple  — determine the memory address of the desired element based on its index.

How does it determine?

To calculate the memory address of an element, Go takes the base memory address of the array (the address of its first element) and adds an offset to it. This offset is determined by the index of the desired element and the size of each element in the array.

The offset for accessing the element at index i in the array is calculated using the formula offset = i * size_of_element where size_of_element represents the size of each element in bytes.

Once the offset is calculated, it is added to the base memory address of the array and this results in the memory address of the desired element:

desired = base address + offset

As a result, this calculation can be performed very quickly by modern processors and the time taken to perform this calculation remains the same.

That’s it!

If you wish to know another example — retrieving data from a Hash Table is a good one.