Computational Complexity

The Purpose of Big O

Big O notation is a theoretical framework used to estimate the efficiency of an algorithm as the input size (n) grows toward infinity. It abstracts away hardware variations, processor speeds, and compiler optimizations, focusing purely on the mathematical scaling profile of the execution logic.

Core Scaling Tiers

Algorithms are classified based on their asymptotic growth curves. Below are the primary complexity models arranged from most efficient to least efficient:

• O(1) — Constant Time: Accessing a value inside an array by index.
• O(log n) — Logarithmic Time: Binary Search inside a sorted array.
• O(n) — Linear Time: Shifting through an unsorted array sequentially.
• O(n log n) — Linearithmic Time: QuickSort and MergeSort.
• O(n²) — Quadratic Time: Bubble Sort or raw matrix comparisons.

Analyzing Code Loops

To calculate time bounds, count how the processing iteration frequency changes relative to the variable n:

// Linear Growth Profile: O(n)
func LinearCheck(n int) {
    for i := 0; i < n; i++ {
        println(i)
    }
}