Analysis Framework & Asymptotic Notations

Analysis of Algorithm Efficiency and Asymptotic Notations

Algorithm analysis investigates how resource consumption—primarily running time and memory space—scales as the input size $n$ grows.

The Analysis Framework

1. Input Size Metric ($n$): The parameter measuring instance size (e.g., number of array items $n$, matrix dimension $n \times n$, or number of bits $b \approx \lfloor \log_2 n \rfloor + 1$).
2. Basic Operation: The operation contributing the most to the total running time, typically the innermost operation inside the deepest loop (e.g., key comparison, arithmetic multiplication).
3. Execution Time Model:

$$T(n) \approx c_{op} \cdot C(n)$$

where $c_{op}$ is the hardware/execution cost of one basic operation, and $C(n)$ is the total count of basic operations executed. 4. Best, Worst, and Average Cases:

• Worst-case $C_{\text{worst}}(n)$: Maximum operations over all inputs of size $n$. Guarantees an upper bound.
• Best-case $C_{\text{best}}(n)$: Minimum operations over all inputs of size $n$.
• Average-case $C_{\text{avg}}(n)$: Expected operations under a defined probability distribution of inputs.

---

Asymptotic Notations ($O, \Omega, \Theta$)

Asymptotic notation abstracts away machine constants and low-order terms, categorizing functions by their order of growth.

Diagram loads as you scroll.

Formal Definitions

1. $O(g(n))$ (Asymptotic Upper Bound): $t(n) \in O(g(n))$ if there exist positive constants $c > 0$ and $n_0 \ge 1$ such that:

   $$t(n) \le c \cdot g(n) \quad \text{for all } n \ge n_0$$

2. $\Omega(g(n))$ (Asymptotic Lower Bound): $t(n) \in \Omega(g(n))$ if there exist positive constants $c > 0$ and $n_0 \ge 1$ such that:

   $$t(n) \ge c \cdot g(n) \quad \text{for all } n \ge n_0$$

3. $\Theta(g(n))$ (Asymptotically Tight Bound): $t(n) \in \Theta(g(n))$ if there exist positive constants $c_1, c_2 > 0$ and $n_0 \ge 1$ such that:

   $$c_1 \cdot g(n) \le t(n) \le c_2 \cdot g(n) \quad \text{for all } n \ge n_0$$

   Equivalently: $t(n) \in \Theta(g(n)) \iff t(n) \in O(g(n)) \text{ and } t(n) \in \Omega(g(n))$.

Limit Quotient Method

To compare orders of growth for $t(n)$ and $g(n)$:

$$L = \lim_{n \to \infty} \frac{t(n)}{g(n)}$$

• If $L = 0$: $t(n)$ has a strictly smaller order of growth than $g(n)$, so $t(n) \in O(g(n))$ and $t(n) \notin \Theta(g(n))$.
• If $L = c > 0$: $t(n)$ and $g(n)$ have the same order of growth, so $t(n) \in \Theta(g(n))$.
• If $L = \infty$: $t(n)$ grows strictly faster than $g(n)$, so $t(n) \in \Omega(g(n))$ and $t(n) \notin O(g(n))$.

Useful tools: L’Hôpital’s Rule $\lim \frac{f(n)}{g(n)} = \lim \frac{f'(n)}{g'(n)}$ and Stirling’s formula $n! \approx \sqrt{2\pi n} \left(\frac{n}{e}\right)^n$.

---

Standard Efficiency Classes

$$c < \log \log n < \log n < n^c \ (0 < c < 1) < n < n \log n < n^2 < n^3 < 2^n < n! < n^n$$

---

Loop Complexity Analysis Patterns

The following patterns represent the classic loop structures tested in algorithm examinations:

Pattern 1: Dependent Nested Loop

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++)
        sum++;
}

Analysis:

$$\sum_{i=1}^n \sum_{j=1}^i 1 = \sum_{i=1}^n i = \frac{n(n+1)}{2} = \Theta(n^2)$$

Pattern 2: Stepped Nested Loop

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j += 4) {
        for (int k = j + 1; k < n; k++)
            count++;
    }
}

Analysis:

• Outer loop runs $n$ times.
• Middle loop runs $\approx (n - i)/4 = \Theta(n)$ times because constant step size $+4$ does not alter asymptotic growth.
• Innermost loop runs $\approx n - j = \Theta(n)$ times.

$$\text{Total} = \Theta(n \times n \times n) = \Theta(n^3)$$

Pattern 3: Quadratic Loop Bound

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n * n; j++)
        count++;
}

Analysis: The inner loop upper bound is $n^2$. For each of the $n$ iterations of $i$, the inner loop executes $\approx n^2$ times:

$$\sum_{i=0}^{n-1} (n^2 - i - 1) \approx n \cdot n^2 = \Theta(n^3)$$

Pattern 4: Repeated Squaring ($j = j \times j$) vs Logarithmic Loops

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) count++;
    for (int k = 0; k < n; k++) {
        for (int j = 2; j <= n; j = j * j)
            count++;
    }
    for (int m = 0; m < n; m++) count++;
}

Analysis:

1. Sequence of values for $j$: $2, 2^2=4, (2^2)^2=16, 2^{2^t} \le n \implies 2^t \le \log_2 n \implies t \le \log_2(\log_2 n)$. Hence, for (j = 2; j <= n; j = j * j) executes $\Theta(\log \log n)$ times.
2. Inside loop $i$, the operations are sequential:
   • First loop: $\Theta(n)$
   • Second nested loop: $n \times \Theta(\log \log n) = \Theta(n \log \log n)$
   • Third loop: $\Theta(n)$
3. Sum per outer iteration = $\Theta(n \log \log n)$. With $n$ outer iterations:

$$\text{Total} = n \cdot \Theta(n \log \log n) = \Theta(n^2 \log \log n)$$

(Note: If the inner step was multiplicative j *= 5, it would be $\Theta(\log_5 n)$, yielding $\Theta(n^2 \log n)$).

Pattern 5: Division Step ($j = j / 2$)

for (int i = 1; i <= n; i++) {
    for (int j = n; j >= 1; j = j / 2)
        sum++;
}

Analysis: Values of $j$: $n, n/2, n/4, \dots, 1$. The number of halving steps until $\le 1$ is $\lfloor \log_2 n \rfloor + 1 = \Theta(\log n)$.

$$\text{Total} = \sum_{i=1}^n \Theta(\log n) = \Theta(n \log n)$$

Pattern 6: Branching Inside Loop

for (int i = 0; i < n; i++) {
    if (i < sqrt(n)) {
        for (int j = 0; j < n; j++) count++;
    } else {
        for (int k = 0; k < n; k++) count++;
    }
}

Analysis: Regardless of whether $i < \sqrt{n}$ (true for $\sqrt{n}$ iterations) or $i \ge \sqrt{n}$ (true for $n - \sqrt{n}$ iterations), exactly one branch is taken, and both branches execute exactly $n$ operations:

$$\text{Work per outer iteration} = \Theta(n) \implies \text{Total} = n \times \Theta(n) = \Theta(n^2)$$

---

Exercises

Exercise 1

Determine whether $2^{n+1} \in O(2^n)$ and whether $2^{2n} \in O(2^n)$. Justify using limits.

Show solution ↓Hide solution ↑

Solution

Part 1:

$$\lim_{n \to \infty} \frac{2^{n+1}}{2^n} = \lim_{n \to \infty} \frac{2 \cdot 2^n}{2^n} = 2$$

Since the limit is a finite positive constant ($L = 2$), $2^{n+1} \in \Theta(2^n) \subseteq O(2^n)$ (True).

Part 2:

$$\lim_{n \to \infty} \frac{2^{2n}}{2^n} = \lim_{n \to \infty} \frac{(2^n)^2}{2^n} = \lim_{n \to \infty} 2^n = \infty$$

Since the limit is $\infty$, $2^{2n} \notin O(2^n)$; rather, $2^{2n} \in \Omega(2^n)$ (False).

Exercise 2

Prove that $\ln n \in O(n^p)$ for any real constant $p > 0$.

Show solution ↓Hide solution ↑

Solution

Using L’Hôpital’s Rule:

$$\lim_{n \to \infty} \frac{\ln n}{n^p} = \lim_{n \to \infty} \frac{\frac{d}{dn}[\ln n]}{\frac{d}{dn}[n^p]} = \lim_{n \to \infty} \frac{1/n}{p \cdot n^{p-1}} = \lim_{n \to \infty} \frac{1}{p \cdot n^p} = 0$$

Because the limit is $0$, $\ln n$ grows strictly slower than any positive power of $n$, confirming $\ln n \in O(n^p)$.