Complexity Analysis Examples
Table of contents
Substitution method
Given the recurrence relation, we can find find the complexity by substituting the complexity of the subproblems.
\[T(n) = \begin{cases} 1 & \text{if } n = 0 \\ 2T(n-1) - 1 & \text{if } n > 0 \end{cases}\]We want to solve
\[T(n) = 2T(n-1) - 1\]Usually, when there is negative work (i.e. $-1$), the Master Theorem idea does not work.
We know that $T(n-1) = 2T(n-2) - 1$ so we can substitute it in.
\[\begin{align*} T(n) &= 2(2T(n-2) - 1) - 1 \\ &= 2^2T(n-2) - 2^1 - 2^0 \end{align*}\]We can continue substituting until we get to $T(0)$,
\[\begin{align*} T(n) &= 2^2T(n-2) - 2^1 - 2^0 \\ &= 2^3T(n-3) - 2^2 - 2^1 - 2^0 \\ ...&= 2^nT(n-n) - 2^{n-1} - 2^{n-2} - ... - 2^1 - 2^0 \\ &= 2^n + 2^n - 2^n - 2^{n-1} - 2^{n-2} - ... - 2^1 - 2^0 \\ &= 2^{n+1} - (2^0 + 2^1 + ... + 2^n) \\ &= 2^{n+1} - \frac{2^{n+1} - 1}{2 - 1} \\ &= 2^{n+1} - 2^{n+1} + 1 \\ &= 1 \end{align*}\]Therefore, $T(n) = O(1)$.
Single while loop
def f(n):
i, x = 1, 1
while x <= n:
i += 1
x += i
The loop runs while $x <= n$.
What is $x$? It is the sum of the first $i$ integers.
Let $k$ be the number of iterations. We want to solve for $k$.
\[\begin{gather*} 1 + 2 + ... + k \le n \\ \frac{k(k+1)}{2} \le n \tag*{Arithmetic series} \\ k \approx O(\sqrt{n}) \end{gather*}\]For loop conditions
Assumes that the work of loop is $O(1)$, unless otherwise stated.
Index square condition
...
for (i = 1; i*i <= n; i++)
...
The loop runs while $i^2 <= n$.
Let $k$ be the number of iterations. We want to solve for $k$.
\[k^2 \le n \implies k \approx O(\sqrt{n})\]Index increase with multiply
...
for (i = 1; i <= n; i *= 2)
...
The loop runs while $i <= n$.
Let $k$ be the number of iterations. We want to solve for $k$.
\[2^k \le n \implies k \approx O(\log n)\]Master theorem
Example 1:
\[T(n) = T(n-2) + O(n^2)\]Since the branching factor of recursion is $1$, each level of recursion does $O(n^2)$ work.
Depth of recursion is $O(n)$ (since $n-2$).
Therefore total work is $O(n) \cdot O(n^2) = O(n^3)$.
Example 2:
\[T(n) = 2T(\frac{n}{2}) + O(nlog n)\]Branching factor is $2 = 2^1$, so each level of recursion does $O(nlog n)$ work.
Depth of recursion is $O(\log n)$ (since $\frac{n}{2}$).
Therefore total work is $O(nlog n) \cdot O(\log n) = O(nlog^2 n)$.
Example 3:
\[T(n) = T(\frac{n}{2}) + T(\frac{n}{4}) + T(\frac{n}{8}) + O(n)\]We can tweak the recurrence to
\[T(n) \le aT(\frac{n}{2}) + O(n)\]We can see that $a < 2^1$, because $\frac{1}{2} > \frac{1}{4} + \frac{1}{8}$.
Work is dominated at the root, so $O(n)$.
Example 3:
\[T(n) = T(\frac{n}{2}) + O(1)\]Since $1 = 2^0$, work is distributed among the tree.
The depth of the tree is $O(\log n)$ (since $\frac{n}{2}$).
Therefore total work is $O(\log n) \cdot O(1) = O(\log n)$.
Example 4:
\[T(n) = T(n-1) + T(n-2) + O(1)\]We can tweak the recurrence to
\[T(n) \le 2T(n-1) + O(1)\]Since $2 > 1$, work is dominated by leaves.
The depth of the tree is $O(n)$ (since $n-1$).
At depth $n$, there are $2^n$ leaves (since $2T(n-1)$).
Therefore total work is $O(1) \cdot O(2^n) = O(2^n)$.
Nested for loops with dependence
Usually with nested loops, we can multiply the complexities.
However, if the inner loop depends on the outer loop, we try to find the number of times the inner loop runs in total.
...
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j += i)
...
As the inner loop condition increases by $i$ each time, we cannot simply multiply the complexities.
We want to solve how many times the inner loop runs in total.
- When $i = 1$, the inner loop runs $n$ times.
- When $i = 2$, the inner loop runs $\frac{n}{2}$ times.
- When $i = 3$, the inner loop runs $\frac{n}{3}$ times.
- When $i = n$, the inner loop runs $\frac{n}{n} = 1$ time.
Then, the inner loop runs in total
\[\begin{align*} \sum_{i=1}^n \frac{n}{i} &= n \sum_{i=1}^n \frac{1}{i} \\ &\approx n \cdot O(\log n) \tag{Harmonic series} \\ &\implies O(n \log n) \end{align*}\]Solving recurrence with change of variable
\[T(n) = 2T(\sqrt{n}) + O(\log n)\]Let $n = 2^m$. Then,
\[\begin{align*} T(n) &= T(2^m) \\ &= 2T(2^{\frac{m}{2}}) + O(m) \end{align*}\]Define $S(m) = T(2^m)$. Then $S(\frac{m}{2}) = T(2^{\frac{m}{2}})$.
Therefore,
\[S(m) = 2S(\frac{m}{2}) + O(m)\]Since $2 = 2^1$, work is distributed among the tree.
The depth of the tree is $O(\log m)$ (since $\frac{m}{2}$).
Thus work is $O(m) \cdot O(\log m) = O(m \log m)$.
Since $2^m = n \implies m = \log n$, it is $O(\log n \log \log n)$.