Solving recurrence equations with repeated substitution?

Question

Say we have a recurrence equation as

$$ T(n) = \begin{cases} T\left(\frac n2\right) +n & \text{if }n\ge2 \\ 1 & \text{if }n=1 \end{cases} $$

Would the first substitution be like this?

$$\left(T\left(\frac n4\right) + \frac n2\right) + n$$

A little confused with these. If you could show the first 3 or so steps, or any other help would be greatly appreciated :)

Related : http://math.stackexchange.com/questions/975064/this-recurrence-relation-will-evaluate-to — lab bhattacharjee, Oct 16 '14 at 03:07

score 0 · Accepted Answer · edited Oct 16 '14 at 00:47

0

Let $n = 2^k$.

$$\begin{align}T\left(n\right) & = T\left(\frac n2\right) + n \\ &= \left[T\left(\frac n4\right) + \frac n2\right] + n\\ & = \left[T\left(\frac n8\right) + \frac n4\right] + \frac n2 + n\\ & = \dots\\ & = T\left(\frac n{2^k}\right) + \left[n + \frac n2 + \frac n4 + \cdots + \frac{n}{2^{k-1}}\right]\\ & = 2n - 1\end{align}$$

edited Oct 16 '14 at 00:47

Edward Jiang

3,670

answered Oct 16 '14 at 00:14

Sean Lo

437

Okay and would nlogn be big theta of this recursive equation? – Vimzy Oct 16 '14 at 00:22

Solving recurrence equations with repeated substitution?

1 Answers1