Introduction to Algorithms & Asymptotic Complexity Analysis

An algorithm is a well-defined, unambiguous sequence of computational steps that transforms an input into a desired output. Algorithm analysis provides mathematical guarantees on resource consumption (time and space), enabling software engineers to design scalable, predictable systems.

⚡ Quick Dive

Complexity Order of Growth (Fastest to Slowest)

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
Constant Logarithmic Linear  Linearithmic Quadratic Exponential Factorial

Asymptotic Notation Reference

Algorithmic Paradigms Summary

📖 Extended Guide

1. The Anatomy of an Algorithm

Every valid algorithm satisfies five fundamental criteria:

1. Finiteness: Terminates after a finite number of steps for all valid inputs.
2. Definiteness: Each step is unambiguous and strictly defined.
3. Input: Accepts zero or more well-specified input quantities.
4. Output: Produces one or more outputs with a defined relationship to inputs.
5. Effectiveness: Operations are basic enough to be computed in finite time (computability).

2. Formal Asymptotic Analysis

When measuring algorithm performance, we ignore hardware clock speeds, memory latency, and compiler optimizations by measuring the growth rate of elementary operations as input size $n \to \infty$.

Execution Time / Operations
    ▲                                             O(n²)
    │                                          .-'
    │                                       .-'
    │                                    .-'      O(n log n)
    │                                 .-'      .-'
    │                              .-'      .-'   O(n)
    │                           .-'      .-'   .-'
    │                        .-'      .-'   .-'
    │                     .-'      .-'   .-'      O(log n)
    │                  .-'      .-'   .-'      .-----------------
    │               .-'      .-'   .-'      .-'   O(1)
    │            .-'      .-'   .-'      .-'   .-----------------
    └───────────┴────────┴─────┴────────┴─────┴─────────────────────► Input Size (n)

Growth Rates Comparison for $n = 1,000,000$:

• $O(1)$: 1 operation (~1 nanosecond)
• $O(\log n)$: $\approx 20$ operations (~20 nanoseconds)
• $O(n)$: $1,000,000$ operations (~1 millisecond)
• $O(n \log n)$: $\approx 20,000,000$ operations (~20 milliseconds)
• $O(n^2)$: $10^{12}$ operations (~16.6 minutes)
• $O(2^n)$: $2^{1,000,000}$ operations (far exceeds atoms in known universe)

3. The Master Theorem for Recurrence Relations

Divide-and-conquer algorithms generate recurrence relations of the form: $$T(n) = aT\left(\frac{n}{b}\right) + f(n)$$ where $a \ge 1$ (number of subproblems), $b > 1$ (subproblem reduction factor), and $f(n)$ is the cost of dividing and combining.

Let $c_{crit} = \log_b a$:

4. Loop Invariants & Correctness Proofs

A loop invariant is a formal mathematical statement about the state of a program that remains true across loop iterations.

To prove an algorithm's correctness, demonstrate three properties:

1. Initialization: The invariant is true prior to the first iteration of the loop.
2. Maintenance: If the invariant is true before an iteration, it remains true before the next iteration.
3. Termination: When the loop terminates, the invariant gives a useful property that helps prove the algorithm is correct.

Example: Binary Search Correctness Proof in Go

package main

import "fmt"

// BinarySearch searches for target in a sorted slice.
// Loop Invariant: If target exists in arr, it must lie within arr[low..high].
func BinarySearch(arr []int, target int) int {
	low, high := 0, len(arr)-1

	// Initialization: low=0, high=len-1. The entire array is the search range.
	for low <= high {
		// Maintenance: Calculate mid without integer overflow
		mid := low + (high-low)/2

		if arr[mid] == target {
			return mid // Found target
		} else if arr[mid] < target {
			low = mid + 1 // Target must be in arr[mid+1..high]
		} else {
			high = mid - 1 // Target must be in arr[low..mid-1]
		}
	}

	// Termination: low > high implies the subarray range is empty.
	// Target does not exist in arr.
	return -1
}

func main() {
	numbers := []int{2, 5, 8, 12, 16, 23, 38, 56, 72, 91}
	target := 23
	fmt.Printf("Index of %d: %d\n", target, BinarySearch(numbers, target))
}

5. Space-Time Tradeoffs & Hardware Reality

Theoretical Big-O analysis must be paired with computer architecture principles:

• Cache Locality: Contiguous memory access ($O(n)$ array traversal) is orders of magnitude faster than pointer chasing ($O(n)$ linked list traversal) due to CPU L1/L2/L3 cache prefetching.
• Auxiliary vs. In-Place Space: In-place algorithms ($O(1)$ auxiliary space) do not allocate proportional memory to process input, preventing Out-Of-Memory (OOM) failures on massive datasets.

📈 Big-O Complexity Reference & Hierarchy

📈 Big O Notation: Writing Efficient Algorithms

Big O Notation is a way to describe the upper bound of an algorithm’s time or space complexity as a function of the input size n. It helps developers measure scalability, performance, and make informed choices.

🔹 O(1) – Constant Time

• The runtime doesn't change as input grows.
• Fastest possible performance.

Examples:

arr[5] // Access element at index
hashMap.put(key, value) // Insert in hash map

✅ Use Case: Hash table lookup, setting a value in a fixed-size array.

🔹 O(n) – Linear Time

• Runtime grows proportionally with the input size.

Examples:

for (int i = 0; i < n; i++) {
    sum += arr[i];
}

✅ Use Case: Looping through an array or list.

🔹 O(log n) – Logarithmic Time

• Each step reduces the problem size in half.

Examples:

// Binary Search
int binarySearch(int[] arr, int target) {
    int low = 0, high = arr.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

✅ Use Case: Binary search, operations on balanced BSTs.

🔹 O(n log n) – Linearithmic Time

• Combines linear and logarithmic growth.
• Most efficient sorting algorithms fall here.

Examples:

Merge Sort, Quick Sort, Heap Sort

✅ Use Case: Large-scale data sorting.

🔹 O(n²) – Quadratic Time

• Performance drops fast as input grows.
• Typically found in nested loops.

Examples:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // Do something
    }
}

✅ Use Case: Simple comparison-based sorting, brute-force string comparison.

🔹 O(n³) – Cubic Time

• Even more nested loops — often in matrix operations.

Examples:

// Naive matrix multiplication
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        for (int k = 0; k < n; k++)
            C[i][j] += A[i][k] * B[k][j];

✅ Use Case: Dense matrix multiplication.

🔹 O(√n) – Square Root Time

• Often seen in mathematical algorithms or optimizations.

Examples:

// Check for prime numbers
for (int i = 2; i <= sqrt(n); i++) {
    if (n % i == 0) return false;
}

✅ Use Case: Sieve of Eratosthenes, divisibility checks.

🔹 O(2ⁿ) – Exponential Time

• Performance becomes infeasible quickly.
• Each step creates 2 new subproblems.

Examples:

// Fibonacci Recursive
int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

❌ Avoid unless input is very small.

🔹 O(n!) – Factorial Time

• Grows faster than any other — used for permutations or brute-force.

Examples:

// Generating permutations of an array

❗ Warning: Explodes with small increases in input size.

📊 Big O Comparison Chart

🧠 Final Tips

• Always strive for the lowest time complexity possible.
• Optimize nested loops, recursion, and data structures used.
• Remember: space complexity matters too (Big O for memory).