🔢 Algorithmic Complexity: Big O From First Principles

🔢 Algorithmic Complexity

Asymptotic Notations

Measures the order of growth of an algorithm with respect to the number of inputs $n$.

• Also called as Landau Notation (Edmund Landau)

Notation	Bound	Common Usage
Big O	Upper Bound	Worst-case complexity
Little o	Upper Strict Bound	Mathematical analysis to show one function grows strictly slower than another
Big $\Omega$	Lower Bound	Best-case or guaranteed lower bound
Little ω	Lower Strict Bound	Mathematical analysis to show one function grows strictly faster than another
Big $\Theta$	Average Bound	Exact asymptotic complexity when both upper and lower bounds match

Example:

$$T(n)=5n^2+3n+20$$

Notation	Result	Meaning
Big $O$	$O(n^2)$	The function grows no faster than $n^2$
Little $o$	$o(n^3)$	The function grows strictly slower than $n^3$
Big $\Omega$	$\Omega(n^2)$	The function grows at least as fast as $n^2$
Little $\omega$	$\omega(n)$	The function grows strictly faster than $n$
Big $\Theta$	$\Theta(n^2)$	The function grows exactly like $n^2$ asymptotically.

Big $O$

Represents the worst-case scenario, where the loop runs till the last element.

• Fastest growing expression determine over all complexity.
• Remove Constant & Remove non-dominant terms

Example.

$$f(n) = An + B \implies O(n)$$ $$f(n) = n^3 + n^2 + 7n \implies O(n^3)$$

Complexity	Operations (n = 1,000,000)	Approx. Time*
$O(1)$	1	1 ns
$O(\log n)$	≈ 20	20 ns
$O(\log^2 n)$	≈ 400	400 ns (0.4 μs)
$O(\sqrt n)$	1,000	1 μs
$O(n)$	1,000,000	1 ms
$O(n \log n)$	≈ 20,000,000	20 ms
$O(n^2)$	1,000,000,000,000	≈ 16.7 minutes
$O(n^3)$	$10^{18}$	≈ 31.7 years

---

Commonly used big O notation

1. Constant time : $O(1)$ -

Amount of work does not grow as the input size grows Fastest,

Independent of $n$

• Single R/W
• Stack push(), pop(), peek()
• Hash table lookup (average case)
• Executes the same number of operations regardless of input size

---

2. Logarithmic : $O(\log n)$ -

An algorithm has logarithmic time complexity when it reduces the problem size by a constant factor in each step, rather than processing every element.

Divide the input by a constant factor (usually 2) each iteration

Common in searching and tree-based algorithms

• Binary Search
• Divide & conquer

Example:

let n = 1024;

while (n > 1) {
  console.log(n);
  n = Math.floor(n / 2);
}

---

3. Poly Logarithmic : $O((\log n)^k)$

If an algorithm performs a logarithmic amount of work multiple times, or has nested logarithmic operations, it often has polylogarithmic complexity

It grows slower than linear O(n) but faster than logarithmic $O(\log n)$.

Example:

let n = 1024;

for (let i = n; i > 1; i = Math.floor(i / 2)) {
for (let j = n; j > 1; j = Math.floor(j / 2)) {
  console.log(i, j);
}
}

1. Polynomial : $O(n^c)$

$c$ nested loops iterating over $n$ elements

Polynomial-time algorithms are generally considered efficient (or tractable) in computer science, especially compared to exponential and factorial algorithms.

Name	Complexity
Linear	$O(n)$
Quadratic	$O(n^2)$
Cubic	$O(n^3)$
Quartic	$O(n^4)$
Quintic	$O(n^5)$
General Polynomial	$O(n^k)$

1.1 Linear : $O(n)$ -

Grows proportionally to input size

• A single Loop iterating over n elements
• As number of elements grow time grows

1.2 Linearithmic : $O(n \ log(n))$

Performs logarithmic work for each of the n elements, or repeatedly divides the problem and then performs linear work during each level of recursion.

Note: not strictly polynomial, but slots in here by growth rate

Faster than quadratic $O(n^2)$ but slower than $O(\log(n))$

Combines linear and logarithmic growth

$O(n) \times O(\log n) = O(n \log n)$

Typical of efficient sorting algorithms

• Merge Sort
• Heap Sort
• Average-case Quick Sort
• Building a balanced Binary Search Tree
• Fast Fourier Transform (FFT)

Example:

let n = 1024;

for (let i = 0; i < n; i++) {                      // O(n)
  for (let j = n; j > 1; j = Math.floor(j / 2)) {  // O(log n)
    console.log(i, j);
  }
}

1.3. Quadratic : $O(n^2)$

Performs $n$ operations for each of the $n$ elements.

$$O(n) \times O(n) = O(n^2)$$

Typical of sorting algorithms

• Bubble Sort: O(n2)
• Selection Sort: O(n2)

Two nested linear loops:

Example:

let n = 1024;

for (let i = 0; i < n; i++) {      // O(n)
  for (let j = 0; j < n; j++) {    // O(n)
    console.log(i, j);
  }
}

1.4. Cubic : $O(n^3)$

Performs $n$ operations for each of the $n^2$ operations, typically due to three nested loops.

Three nested linear loops

• Naive matrix multiplication
• Floyd-Warshall shortest path algorithm
• Comparing every triplet of elements
• Brute-force solutions involving three independent variables

Example:

  let n = 100;
  
  for (let i = 0; i < n; i++) {          // O(n)
    for (let j = 0; j < n; j++) {        // O(n)
      for (let k = 0; k < n; k++) {      // O(n)
        console.log(i, j, k);
      }
    }
  }

---

2. Exponential : $O(c^n)$

For each element run $c$ nested loops

• Running time doubles, triples, or generally multiplies by a constant with each additional input
• Typically caused by recursive branching
• Becomes impractical even for moderate input sizes

If each recursive call branches into a constant number $(c>1)$ of new recursive calls, the algorithm usually has exponential time complexity, $O(c^n)$.

Example:

function solve(n) {
  if (n === 0) return;

  solve(n - 1);
  solve(n - 1);
}

solve(5);

$O(c^n)$ grows faster than $O(n^c)$.

If $O(n^c)$ grows faster than $O(c^n)$ then it is called superpolynomial, and in that case $O(c^n)$ is called subexponential.

---

3. Factorial : $O(n!)$

explores every possible ordering (permutation) of the input elements.

• Generating all permutations
• Brute-force Traveling Salesman Problem (TSP)
• Brute-force scheduling and assignment problems
• Exhaustive search over all possible orderings

Factorial growth is even faster than exponential growth. It becomes impractical for surprisingly small values of n.

$$n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1 = n!$$

Example;

function permute(arr, start = 0) {
  if (start === arr.length) {
    console.log(arr.join(" "));
    return;
  }

  for (let i = start; i < arr.length; i++) {
    [arr[start], arr[i]] = [arr[i], arr[start]];

    permute(arr, start + 1);

    [arr[start], arr[i]] = [arr[i], arr[start]];
  }
}

permute([1, 2, 3]);

If an algorithm has factorial complexity,

• first ask whether it's recomputing the same work or exploring impossible solutions.
• Memoization, dynamic programming, and pruning are the most common ways to reduce O(n!) to a much more practical complexity.

---

Related Posts

• 🧱 Data Structures — the structures whose Access/Insertion/Deletion/Search columns use this exact Big O notation
• 🔎 Searching Algorithms — Binary Search's $O(\log n)$ is the logarithmic case worked through here
• ⚡ Sorting Algorithms — Merge Sort/Quick Sort's $O(n \log n)$ is the linearithmic case worked through here