Analyze Recurrences

The Iteration Method

Steps:

Given that:

T(n) = c + T(n/2)

Firstly, expand it.

\begin{align*} T(n) &= c + T(n/2) \\ &= c + c + T(n/4) \\ &= c + c + c + T(n/8) \\ &= \dots \\ &= kc + T(n/2^k) \end{align*}

Then, assume that:

n = 2^k \Longrightarrow k = \log{n}

Finally, substitute it to the original expression:

\begin{align*} T(n) &= kc + T(n/2^k) \\ &= c\log{n} + T(n/2^{\log{n}}) \\ &= c\log{n} + T(1) \\ &= O(\log{n}) \end{align*}

Given that:

T(n) = \begin{cases} 1 &n=1 \\ T(n-1) + \log{n} &n>1 \end{cases}

Then

\begin{align*} T(n) &= T(n-1) + \log{n} \\ &= T(n-2) + \log{n} + \log{n-1} \\ &= \dots \\ &= T(n-k) + \sum_{i=1}^{n}{\log{i}} \\ &= T(n-k) + \log{(n!)} \\ \end{align*}

Since when $n=1$ , $T(n) = 1$ , so we assume that $k = n - 1$ finally.

Then

T(n) = T(1) + \log{(n!)} = 1 + \log{(n!)}

Use Stirling’s formula,

\begin{align*} \log{n} &= n\log{n} - n\log{e} + O(\log{n}) \\ T(n) &= 1 + \log{(n!)} \\ T(n) &= 1 + n\log{n} - n\log{e} + O(\log{n}) \\ T(n) &= O(n\log{n}) \end{align*}

Steps:

Given that

T(n) = 2T(\frac{n}{2}) + n

Firstly, we guess that $T(n) \in O(n\log{n})$

So we need to prove that $T(n) \le c \cdot n\log{n}$

Assume that

T(\frac{n}{2}) \le c \cdot \frac{n}{2}\log{\frac{n}{2}}

Then the inductive steps are:

\begin{align*} T(n) &= 2T(\frac{n}{2}) + n \\ &\le 2(c \cdot \frac{n}{2}\log{\frac{n}{2}}) + n \\ &= cn\log{\frac{n}{2}} + n \\ &= cn(\log{n} - 1) + n \\ &= cn\log{n} - (c - 1)n \\ &\le cn\log{n} \quad \forall c \ge 1 \\ \therefore T(n) &\in O(n\log{n}) \end{align*}

Draw the recursion tree and calculate the cost of each level which start at $0$ .

Suppose that we have:

T(n) = aT(\frac{n}{b}) + f(n) \quad a \ge 1, b \gt 1

Then we have three theorems:

If $f(n) = O(n^{\log_b{a} - \epsilon})$ , then $T(n) = \Theta(n^{\log_b{a}})$
If $f(n) = \Theta(n^{\log_b{a}})$ , then $T(n) = \Theta(n^{\log_b{a}}\log{n})$
If $f(n) = \Omega(n^{\log_b{a} + \epsilon})$ , and if $af(\frac{n}{b}) \le cf(n)$ for some $c \lt 1$ , and all sufficiently large $n$ , then $T(n)=\Theta(f(n))$ .

Given that

T(n) = 2T(\frac{n}{2}) + n

Then

\begin{align*} a = 2, b &= 2, f(n) = n \\ n^{\log_b{a}} &= n \\ n^{\log_b{a}} &= f(n) \\ \therefore T(n) &= \Theta(n^{\log_b{a}}\log{n}) \\ &= \Theta(n\log(n)) \end{align*}

Given that

T(n) = 9T(\frac{n}{3}) + n

Then

\begin{align*} a = 9, b &=3, f(n) = n \\ n^{\log_b{a}} &= n^2 \\ n^{\log_b{a}} &\ge f(n) = n \\ \therefore f(n) &= O(n^{\log_b{a} - \epsilon}) \\ &= O(n^{2 - \epsilon}) \\ \therefore T(n) &= \Theta(n^2) \end{align*}

Given that

T(n) = 3T(\frac{n}{4}) + n\log{n}

Then

\begin{align*} a = 3, b &= 4, f(n) = n\log{n} \\ n^{log_b{a}} &= n^{log_4{3}} \lt n \lt f(n) \\ \end{align*}

Before applying case 3, we need to check the regularity condition, which means that $af(\frac{n}{b}) \le cf(n)$ where $c \lt 1$ should be true.

\begin{align*} af(\frac{n}{b}) &= 3f(\frac{n}{4}) \\ &= \frac{3}{4}n\log{\frac{n}{4}} \\ cf(n) &= cn\log{n} \\ \therefore \frac{3}{4}n\log{\frac{n}{4}} &\le cn\log{n} \\ \end{align*}

When $c = \frac{3}{4}$ , the expression is true. So the condition check is successfully.

\begin{align*} f(n) &= \Omega(n^{\log_b{a} + \epsilon}) = \Omega(n^{\log_{4}{3} + \epsilon}) \\ \therefore T(n) &= \Theta(f(n)) \\ &= \Theta(n\log{n}) \end{align*}

Last updated on October 27, 2025