Eventually Bitwise

Time Complexity

Overview

Time complexity is a theoretical measure that describes the amount of computer time it takes to run an algorithm as a function of the length of the input. Instead of measuring actual seconds (which vary by hardware), time complexity counts the number of elementary operations performed.

Core Concepts

  • Elementary Operations: Operations that take a constant amount of time, such as:
    • Assigning a value to a variable.
    • Performing an arithmetic operation (+, -, *, /).
    • Comparing two values.
    • Returning from a function.
  • Counting Operations: To determine time complexity, you analyze the code to see how many times these operations are executed relative to the input size $n$.
    • A single loop from $0$ to $n$ results in $O(n)$ operations.
    • Nested loops (one inside another) typically result in $O(n^2)$ operations.
  • Growth Rate: Time complexity focuses on the “growth rate”—how the time increases as $n$ becomes very large. This is why constants are ignored (e.g., $2n + 5$ operations is simplified to $O(n)$).
  • Time Complexity vs. Wall-Clock Time:
    • Time Complexity: Theoretical; hardware-independent.
    • Wall-Clock Time: Actual time elapsed; dependent on CPU speed, memory latency, and other running processes.

Code Examples

// Analysis: 1 operation -> O(1)
function isEven(n: number): boolean {
    return n % 2 === 0; 
}

// Analysis: n operations (loop runs n times) -> O(n)
function findMax(arr: number[]): number {
    let max = arr[0];
    for (let i = 1; i < arr.length; i++) { // n-1 iterations
        if (arr[i] > max) max = arr[i];   // constant time operation
    }
    return max;
}

// Analysis: n * n operations -> O(n^2)
function bubbleSort(arr: number[]) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j+1]) [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
        }
    }
}

Use Cases

  • Performance Bottleneck Identification: Determining which part of a program will slow down the most as data grows.
  • Algorithm Selection: Choosing the most efficient algorithm for a given input size (e.g., using an $O(n \log n)$ sort instead of an $O(n^2)$ sort for large lists).

Gotchas

  • Hidden Costs: Some built-in language functions have their own time complexity (e.g., .shift() in a JavaScript array is $O(n)$, not $O(1)$).
  • Best vs. Worst Case: An algorithm might be very fast for some inputs (Best Case) but very slow for others (Worst Case). Time complexity usually refers to the Worst Case unless specified otherwise.

Related Notes

, ,