AntInLoop

Time & Space Complexity Analysis (Big-O)

Asymptotic Complexity Analysis uses Big-O, Big-Omega, and Big-Theta notation to bound an algorithm's runtime and memory growth as input size n scales, guiding algorithm selection from input constraints.

Difficulty: Easy · Interactive Visualizer · C++ / Python / Java / JS Code

Time & Space Complexity Analysis (Big-O)

Asymptotic Complexity Analysis measures how an algorithm's operations and memory scale as input size $n \to \infty$, ignoring hardware-dependent constant factors:

  • $O(f(n))$ (Big-O): Asymptotic upper bound (worst case).
  • $\Omega(f(n))$ (Big-Omega): Asymptotic lower bound.
  • $\Theta(f(n))$ (Big-Theta): Asymptotic tight bound (both $O$ and $\Omega$).

Constraint-to-Complexity Cheat Sheet (~$10^8$ Ops / Second)

| Input Size $n$ | Max Acceptable Complexity | Typical Algorithms |

| :--- | :---: | :--- |

| $n \le 12$ | $O(n!)$ | Permutations, N-Queens |

| $n \le 20$ | $O(2^n \cdot n)$ | Bitmask DP, Subsets |

| $n \le 500$ | $O(n^3)$ | Floyd–Warshall, Matrix Chain |

| $n \le 5{,}000$ | $O(n^2)$ | 2D DP (LCS, Edit Distance) |

| $n \le 10^5$ | $O(n \sqrt{n})$ | Sqrt Decomposition, Mo's Algorithm |

| $n \le 10^6$ | $O(n \log n)$ or $O(n)$ | Merge Sort, Segment Tree, BFS/DFS |

| $n \le 10^{18}$ | $O(\log n)$ or $O(1)$ | Binary Search, Fast Exponentiation, Digit DP |

---

Amortized Analysis Example: Dynamic Array Doubling

Even though resizing a std::vector copies $n$ elements in $O(n)$ worst case, doubling capacity ($1, 2, 4, \dots, n$) copies

Loading AntInLoop...

lt; 2n$ elements across $n$ insertions—giving $O(1)$ amortized cost per push_back!

<details>

<summary>Show C++ Demonstration</summary>

#include <iostream>

int main() {
    int cap = 1, copies = 0, n = 1024;
    for (int sz = 0; sz < n; ++sz) {
        if (sz == cap) { copies += cap; cap *= 2; }
    }
    std::cout << "Total copies for " << n << " appends: " << copies
              << " (< 2*n, amortized O(1)!)\n";
    return 0;
}

</details>

---

Related Algorithms