Big O Complexity Analyzer

Big O notation describes the upper bound of an algorithm's time or space requirements as the input size n grows toward infinity. It ignores constants and lower-order terms to focus on the dominant growth factor. O(1) is constant, O(log n) is logarithmic, O(n) is linear, O(n log n) is log-linear, O(n²) is quadratic, O(2ⁿ) is exponential.

Worst case (most common for Big O) describes the maximum time/space for any input of size n. Average case (often Θ notation) describes expected performance across typical inputs. Best case (Ω notation) describes the minimum. For example, quicksort has O(n²) worst case but O(n log n) average case. Big O typically refers to worst case unless specified.

Constants depend on hardware, compiler, and implementation details, so they're not useful for comparing algorithms at scale. O(2n) and O(1000n) are both O(n) because both grow linearly — for large enough n, the constant factor matters less than the growth rate. When constants are large and n is small, profiling actual code is more useful than asymptotic analysis.

Time complexity measures how many operations an algorithm performs relative to input size. Space complexity measures how much memory it uses. An algorithm can trade one for the other — memoization (dynamic programming) reduces time from O(2ⁿ) to O(n) but uses O(n) space. Always analyse both when choosing an algorithm.

Each nested loop multiplies the complexity. A single loop over n elements is O(n). Two nested loops are O(n²). Three nested loops are O(n³). Loops that halve their range each iteration are O(log n). A loop over n with an inner binary search is O(n log n). The key is identifying whether inner loops depend on the outer loop variable.