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

Big-O Addition Rule: Prove $f_1(n)+f_2(n)=O(g_1(n)+g_2(n))$

Binary Search Complexity: Why the Correct Choice is $O(\log n)$

Differentiating Divide & Conquer, Greedy Method, and Dynamic Programming

Browse all research articles