Unit 1: Behaviour Analysis of Algorithms

1. Architectural Foundations of Algorithmic Behaviour

The Random Access Machine (RAM) Model

In computational complexity and competitive coding, algorithmic performance is analyzed against an idealized hardware model termed the Random Access Machine (RAM):

• Memory consists of an unbounded array of uniform memory cells, each capable of holding an integer or pointer of standard word size ($w$ bits, typically 32 or 64 bits).
• Basic scalar operations execute in strictly $O(1)$ constant time:
  • Arithmetic operations: addition, subtraction, multiplication, integer division, modulo (+, -, *, /, %).
  • Bitwise operations: shifts, bitwise AND, OR, XOR (<<, >>, &, |, ^, ~).
  • Pointer dereferencing, indexing, and assignment.
• Operations on arbitrary-precision numbers (strings or big-integers with $L$ digits) are not $O(1)$; they scale as $O(L)$ or $O(L \log L)$.

Mathematical Limit Hierarchy

The relative asymptotic growth rate of two complexity functions $f(n)$ and $g(n)$ as input size $n \to \infty$ is rigorously evaluated using L'Hôpital's rule and mathematical limits:
$L = \lim_{n \to \infty} \frac{f(n)}{g(n)}$

1. $L = 0$: $f(n)$ grows strictly slower than $g(n)$ ($f(n) \in o(g(n))$).
2. $0 < L < \infty$: $f(n)$ and $g(n)$ have identical asymptotic rates of growth ($f(n) \in \Theta(g(n))$).
3. $L = \infty$: $f(n)$ grows strictly faster than $g(n)$ ($f(n) \in \omega(g(n))$).

2. Asymptotic Notations: Formal Definitions and Set Theory

Asymptotic Upper Bound: Big-O ($O$)

$f(n) \in O(g(n))$ if and only if there exist positive constants $c > 0$ and $n_0 \ge 1$ such that:
$0 \le f(n) \le c \cdot g(n) \quad \text{for all } n \ge n_0$
Big-O provides a worst-case asymptotic ceiling on resource growth.

Asymptotic Lower Bound: Big-Omega ($\Omega$)

$f(n) \in \Omega(g(n))$ if and only if there exist positive constants $c > 0$ and $n_0 \ge 1$ such that:
$0 \le c \cdot g(n) \le f(n) \quad \text{for all } n \ge n_0$
Big-Omega represents an asymptotic floor beneath which the function cannot drop for large $n$.

Asymptotically Tight Bound: Big-Theta ($\Theta$)

$f(n) \in \Theta(g(n))$ if and only if $f(n) \in O(g(n))$ and $f(n) \in \Omega(g(n))$. Formally:
$0 \le c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n) \quad \text{for all } n \ge n_0$

Strict Asymptotic Bounds: Little-o ($o$) and Little-omega ($\omega$)

• Little-o ($o$): $f(n) \in o(g(n))$ means for every positive constant $c > 0$, there exists $n_0$ such that $0 \le f(n) < c \cdot g(n)$ for all $n \ge n_0$. Equivalently, $\lim_{n \to \infty} f(n)/g(n) = 0$.
• Little-omega ($\omega$): $f(n) \in \omega(g(n))$ means $\lim_{n \to \infty} f(n)/g(n) = \infty$.

3. The Canonical Complexity Class Hierarchy

Ranked from slowest growing (most efficient) to fastest exploding:
$O(1) < O(\log \log n) < O(\log n) < O(\sqrt{n}) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$

• Constant $O(1)$: Hash table lookup, stack push/pop, array indexing.
• Double Logarithmic $O(\log \log n)$: Interpolation search, van Emde Boas trees.
• Logarithmic $O(\log n)$: Binary search, balanced BST operations, binary exponentiation.
• Square Root $O(\sqrt{n})$: Trial division primality testing, Mo's algorithm, square root decomposition.
• Linear $O(n)$: Two pointers, Kadane's algorithm, prefix sum construction, linear sieve.
• Linearithmic $O(n \log n)$: Merge sort, quicksort (average), segment tree construction.
• Polynomial $O(n^2), O(n^3)$: Nested grid iterations, Floyd-Warshall, matrix multiplication.
• Exponential & Factorial $O(2^n), O(n!)$: Subsets, bitmask DP, permutations, exhaustive brute force.

4. Analysis Paradigms: Worst, Average, Best, and Amortized

Input-Dependent Behaviors

1. Worst-Case Analysis $T_{\text{worst}}(n)$: The maximum number of basic operations taken over all possible inputs of size $n$. This is the standard metric in competitive programming because contest judges deliberately submit adversarial test cases.
2. Average-Case Analysis $T_{\text{avg}}(n)$: The expected value $\mathbb{E}[T(I)]$ over a probabilistic distribution of inputs. For example, randomized Quicksort runs in $O(n \log n)$ expected time.
3. Best-Case Analysis $T_{\text{best}}(n)$: The minimum number of steps taken over any input of size $n$ (e.g., $O(n)$ for insertion sort on an already sorted array).

Amortized Analysis Techniques

Amortized analysis averages the running time of a sequence of operations over time, guaranteeing an average cost per operation even if individual steps are occasionally expensive:

1. Aggregate Method: Show that a sequence of $k$ operations takes $T(k)$ total time in the worst case; the amortized cost per operation is $T(k) / k$.
2. Accounting (Banker's) Method: Charge artificial credits (amortized cost) to cheap operations. These stored credits pay for subsequent expensive operations.
3. Potential Method (Physicist's Method): Define a potential function $\Phi(D)$ mapping the data structure state to a non-negative real number ($\Phi(D_0) = 0, \Phi(D_i) \ge 0$). The amortized cost of the $i$-th operation is:
   $\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1})$
   Summing over $k$ operations: $\sum_{i=1}^k \hat{c}_i = \sum_{i=1}^k c_i + \Phi(D_k) - \Phi(D_0) \ge \sum_{i=1}^k c_i$.

5. Practical Competitive Programming Budgets and Scaling Rules

The $10^8$ Operations Per Second Benchmark

Standard online judge CPU cores (Codeforces, AtCoder, CSES, LeetCode) execute roughly $10^8$ simple integer/bitwise operations per second:

• Time Limit = $1.0$ second $\implies \approx 10^8$ operations.
• Time Limit = $2.0$ seconds $\implies \approx 2 \times 10^8$ operations.

Input Constraint-to-Algorithm Mapping Table

Memory Budgeting and Stack Overflow Prevention

• Memory Limit: Typically $256$ MB.
  • $1 \text{ MB} = 1024 \times 1024 \text{ bytes} \approx 10^6 \text{ bytes}$.
  • A 32-bit int takes 4 bytes. An array of $10^7$ integers takes $40$ MB.
  • An array of size $10^8$ integers consumes $400$ MB, triggering Memory Limit Exceeded (MLE).
• Call Stack Limit: Linux platforms allocate an 8 MB default stack. Recursive depth exceeding $10^5$ nested frames triggers Runtime Error / Stack Overflow (SIGSEGV). Deep recursions (DFS on trees/graphs) must be converted to iterative stacks or use custom stack pragmas.