Big-O Notation & Analysis

Big-O notation is the standard mathematical vocabulary used in Computer Science to describe the performance and efficiency of an algorithm. Specifically, it describes the worst-case scenario—how the runtime (Time Complexity) or memory usage (Space Complexity) scales as the input size ($N$) grows towards infinity.

Why Do We Use It?

If you run an algorithm on a supercomputer, it might take 1 millisecond. If you run it on a 10-year-old laptop, it might take 10 seconds. Time measured in seconds is relative to the hardware. Big-O is hardware-independent. It counts the number of fundamental operations an algorithm performs relative to the size of the input.

Common Time Complexities (From Best to Worst)

1. $O(1)$ - Constant Time

The algorithm takes the exact same amount of time regardless of the input size.

function getFirstElement(arr: number[]): number {
  return arr[0]; // Always takes 1 operation, whether array size is 10 or 10,000,000
}

2. $O(\log N)$ - Logarithmic Time

The algorithm drastically reduces the problem size with each step (usually by dividing it in half). Extremely efficient for large datasets.

function binarySearch(arr: number[], target: number): boolean {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return true;
    if (arr[mid] < target) left = mid + 1; // Discard left half
    else right = mid - 1;                  // Discard right half
  }
  return false;
}

3. $O(N)$ - Linear Time

The algorithm's time scales directly in proportion to the input size. If the input doubles, the time doubles.

function findMax(arr: number[]): number {
  let max = -Infinity;
  for (let i = 0; i < arr.length; i++) { // Loops exactly N times
    if (arr[i] > max) max = arr[i];
  }
  return max;
}

4. $O(N \log N)$ - Linearithmic Time

Commonly seen in highly optimized sorting algorithms like Merge Sort and Quick Sort. It means performing an $O(\log N)$ operation $N$ times.

5. $O(N^2)$ - Quadratic Time

Usually involves nested loops. Poor performance for large datasets. Seen in basic sorting algorithms like Bubble Sort.

function printAllPairs(arr: number[]): void {
  for (let i = 0; i < arr.length; i++) {       // Outer loop runs N times
    for (let j = 0; j < arr.length; j++) {     // Inner loop runs N times
      console.log(`${arr[i]}, ${arr[j]}`);     // Total operations: N * N = N^2
    }
  }
}

6. $O(2^N)$ - Exponential Time

The number of operations doubles with every single addition to the input. Terribly slow. Often seen in naive recursive solutions to the Fibonacci sequence or the Traveling Salesperson Problem.

Best, Average, and Worst Cases

• Worst Case (Big-O): The maximum number of operations an algorithm could possibly perform. (e.g., searching for an element in an array and it's at the very end).
• Best Case (Omega - $\Omega$): The minimum number of operations. (e.g., searching an array and finding the element at index 0).
• Average Case (Theta - $\Theta$): The expected number of operations on average over all possible inputs.

Space Complexity

Space complexity measures the extra memory required by the algorithm as the input grows. It follows the exact same Big-O rules.

• $O(1)$ Space: The algorithm only uses a few fixed variables, regardless of input size. (e.g., a simple for loop modifying an array in-place).
• $O(N)$ Space: The algorithm allocates memory proportional to the input size. (e.g., duplicating the input array or building a hash map of all elements).