Time Complexity via Divide-and-Conquer Recurrences Two Worked Examples | AI Research

Time Complexity via Divide-and-Conquer Recurrences (Two Worked Examples)

Verified Sources

Sep 12, 2026

This section teaches how to compute asymptotic running time for two recurrences—one “variable-size divide-and-conquer” and one “incremental” recurrence.

We will solve:

$(i)\quad T(n)=\sqrt{n}\,T(\sqrt{n})+n,\quad n>2$
$(ii)\quad T(n)=T(n-1)+\frac{1}{n},\quad n>1$

We’ll use a standard “recurrence tree / unfolding” strategy for (i) and summation (telescoping / series) for (ii).

type="tip" title="Pro Tip" content="When the subproblem size changes nonlinearly (like $\sqrt{n}$ ), switch from Master Theorem to recurrence-tree/unrolling and track how many levels occur and what each level costs."

Key keywords you’ll use

Recurrence
Recurrence tree
Unrolling
Base case

(Next, we do the full derivations.)

Solve (i) T(n)=√n·T(√n)+n via recurrence-tree unrolling

1
Step 1
Let $n_0=n$ and define $n_{i+1}=\sqrt{n_i}$ , so $n_i=n^{(1/2^i)}$ .
2
Step 2
At level $i$ , the recurrence contributes a factor of $\sqrt{n_i}$ in front of the next $T(·)$ . Since $n_i=n^{1/2^i}$ , we get $\sqrt{n_i}=n^{1/2^{i+1}}$ .
3
Step 3
At each level, the additive term contributes $+n_i$ (because the '+n' in $T(n)$ becomes '+(current subproblem size)' when unfolded).
4
Step 4
Stop when $n_i \le 2$ (or any constant). Solve $n^{1/2^i} \le c$ → $\frac{1}{2^i}\ln n \le \ln c$ → $2^i \ge \Theta(\ln n)$ , hence $i=\Theta(\log\log n)$ .
5
Step 5
Total cost is approximately $\sum_{i=0}^{\Theta(\log\log n)} \left(\prod_{j=0}^{i-1} \sqrt{n_j}\right)\cdot n_i$ Using $\prod_{j=0}^{i-1} \sqrt{n_j}=\prod_{j=0}^{i-1} n^{1/2^{j+1}}=n^{\sum_{j=0}^{i-1} 1/2^{j+1}}=n^{1-1/2^i}.$ Thus the level- $i$ term becomes $n^{1-1/2^i}\cdot n^{1/2^i}=n$ .
6
Step 6
Each level contributes $\Theta(n)$ , and there are $\Theta(\log\log n)$ levels, so $T(n)=\Theta(n\log\log n).$

Result for (i)

$T(n)=\sqrt{n}\,T(\sqrt{n})+n \quad \\Longrightarrow \\quad T(n)=\Theta(n\\log\\log n).$

Why this happens (intuition):
Unrolling produces about $\\log\\log n$ levels because each step takes a square root, so the exponent $1/2^i$ shrinks geometrically. Meanwhile, although the subproblem sizes shrink, the multiplicative factor from $\\sqrt{n}$ expands in exactly the right way so that the effective cost per level stays on the order of $n$ .

type="warning" title="Common Pitfall" content="Do NOT apply the standard Master Theorem directly here: the subproblem size is $\sqrt{n}$ but the number of subproblems is effectively variable (the multiplier is $\sqrt{n}$ , not a constant $a$ ). That’s why recurrence-tree accounting/unrolling is safer."

Solve (ii) T(n)=T(n-1)+1/n using telescoping unrolling

1
Step 1
"For $n>1$ iterate: $T(n)=T(n-1)+\frac{1}{n} = T(n-2)+\frac{1}{n-1}+\frac{1}{n}=\cdots= T(1)+\sum_{k=2}^{n}\frac{1}{k}.$
2
Step 2
"Let $H_n=\sum_{k=1}^{n}\frac{1}{k}$ . Then $\sum_{k=2}^{n}\frac{1}{k}=H_n-1.$
3
Step 3
A standard fact is $H_n=\Theta(\log n)$ , so $T(n)=T(1)+\Theta(\log n)=\Theta(\log n).$

Result for (ii)

$T(n)=T(n-1)+\\frac{1}{n} \quad \\Longrightarrow \\quad T(n)=\\Theta(\\log n).$

Intuition:
You add $1/n$ each step. Summing $1/k$ from $k=2$ to $n$ yields the harmonic series, which grows logarithmically.

Asymptotic running time comparison

Two different recurrence styles yield distinct growth rates.

Learning roadmap for these recurrence types

Identify recurrence structure

Step A

Check whether coefficients/subproblem sizes are constant or variable (e.g., $\sqrt{n}$ multiplier)."

Choose the right method

Step B

Use unrolling/recurrence tree for variable divide-and-conquer; use telescoping/sums for linear recurrences."

Count levels and sum per level

Step C

For $\sqrt{n}$ -style recurrences, levels are about $\Theta(\log\log n)$ ."

Convert sums to known series

Step D

For $\sum 1/k$ , use harmonic growth $\Theta(\log n)$ ."

FAQs and edge cases

Knowledge Check

Question 1 of 4

Q1Single choice

For $T(n)=\sqrt{n}\,T(\sqrt{n})+n$ , the number of recurrence-tree levels is approximately:

$\Theta(\log n)$

$\Theta(\log\log n)$

$\Theta(\sqrt{n})$

$\Theta(n)$

Explore Related Topics

Complexity Analysis: Best Case, Worst Case, and Average Case

The material introduces best‑case, worst‑case, and average‑case complexity as three distinct functions describing an algorithm’s running time on inputs of size  $n$ , explains how they are formally defined, and shows why worst‑case analysis is usually preferred.

Best case: $T_{\text{best}}(n)=\min_{I\in\mathcal I_n} T(I)$ , the minimum time over all inputs of size  $n$ .
Worst case: $T_{\text{worst}}(n)=\max_{I\in\mathcal I_n} T(I)$ , giving a guaranteed upper bound.
Average case: $T_{\text{avg}}(n)=\sum_{I\in\mathcal I_n}P(I)\,T(I)$ , requiring an explicit input probability model.
Linear search illustrates the three cases: $\Theta(1)$ best, $\Theta(n)$ worst, and $\Theta(n)$ average (expected $\frac{n+1}{2}$ comparisons).
Worst‑case analysis is favored because it needs no probabilistic assumptions and ensures reliability for all inputs, especially in real‑time or safety‑critical systems.

Differentiating Divide & Conquer, Greedy Method, and Dynamic Programming

Mastering Recurrence Relations: The Substitution Method

The lesson shows how to solve the classic recurrence  $T(n)=2T(n/2)+n$ with the substitution method, using a recursion‑tree intuition to guess an $O(n\log n)$ bound and then proving it by induction.

Each level of the recursion tree costs $n$ , and there are $\log_2 n$ levels → total $Θ(n\log n)$ .
Inductive hypothesis: $T(n)\le c\,n\log_2 n$ for $n\ge n_0$ , which simplifies to $c\ge1$ in the induction step.
The base case must start at $n_0>1$ (e.g., $n_0=2$ ) because $T(1)\le c\cdot1\log_2 1$ is false.
Substitution offers rigorous proof, while recursion trees give quick guesses; the Master Theorem confirms $T(n)=Θ(n\log n)$ .

Browse all research articles