Time Complexity: Measuring Algorithm Performance

Definition

Time complexity quantifies the growth in execution time of an algoirthm as the input size increases, independent of environmental factors. It is represented using a function $f(n)$, where $n$ is the data scale.

Asymptotic Upper Bound (Big O Notation)

Describes the worst-case growth rate. For $f(n)$, simplify to $g(n)$ by:

• Omitting constant multipliers (e.g., $3n \to n$).
• Ignoring lower-order terms in polynomials (e.g., $n^2 + n \to n^2$).
• Standardizing logarithms to base 2 (e.g., $\log_b n \to \log_2 n$, as constants from change of base are omitted).
• Removing constant exponents in logs (e.g., $\log n^c \to c\log n$).

Examples

Linear Search: $f(n) = 3n + 3$. Simplifies to $g(n) = n$, so $O(n)$.
Binary Search: $f(n) = 5\lfloor\log_2 n\rfloor + 9$. Simplifies to $g(n) = \log_2 n$, so $O(\log n)$.

Common Big O Notations

• $O(1)$: Constant time (no dependency on $n$).
• $O(\log n)$: Logarithmic time.
• $O(n)$: Linear time (proportional to $n$).
• $O(n\log n)$: Quasilinear time.
• $O(n^2)$: Quadratic time.
• $O(2^n)$: Exponential time.
• $O(n!)$: Factorial time (highest complexity).

Asymptoitc Lower Bound (Omega Notation, Ω)

Represents the best-case growth rate. Denoted $\Omega(g(n))$ if $f(n) \geq cg(n)$ for some constant $c$ and sufficiently large $n$.

Tight Bound (Theta Notation, Θ)

Combines upper and lower bounds. Denoted $\Theta(g(n))$ if $c_1g(n) \leq f(n) \leq c_2g(n)$ for constants $c_1, c_2$ and large $n$. Pronounced "theta".

Space Complexity: Measuring Auxiliary Resource Usage

Dfeinition

Similar to time complexity, space complexity uses Big O to quantify the growth in additional memory usage as input size increases.

Example: Binary Search Space Analysis

Consider a method finding a target in a sorted array:

private static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;  // Pointers: 2 variables
    while (left <= right) {
        int mid = left + (right - left) / 2;  // Avoid overflow vs (left+right)/2
        if (target < arr[mid]) {
            right = mid - 1;
        } else if (target > arr[mid]) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;  // Loop uses 1 variable (mid)
}

Auxiliary space: 3 integer pointers (left, right, mid) → constant $O(1)$.

Binary Search Performance Summary

Time Complexity

• Worst Case: $O(\log n)$ (element at array end).
• Best Case: $O(1)$ (element at midpoint, single iteration).

Space Complexity

Uses constant extra space for pointers → $O(1)$.