# Solve the recurrence: t(n) = t(n/2) + n + 2 (Solution included).

## Homework Statement

The problem along with its solution is attached as Problem.jpg.

## Homework Equations

Recurrence relation.

## The Attempt at a Solution

I am confused as to what the solution is stating. I get up to and including (3) but I am stuck at (4). After (4), I get that k = log2(n) because n = 2^k = 2^(log2(n)) = n.

I would greatly appreciate it if someone could help me get unstuck!

#### Attachments

• 20.2 KB Views: 370
Last edited:

Related Engineering and Comp Sci Homework Help News on Phys.org

## Homework Statement

The problem along with its solution is attached as Problem.jpg.

## Homework Equations

Recurrence relation.

## The Attempt at a Solution

I am confused as to what the solution is stating. I get up to and including (3) but I am stuck at (4). After (4), I get that k = log2(n) because n = 2^k = 2^(log2(n)) = n.

I would greatly appreciate it if someone could help me get unstuck!
You forgot to attach Problem.jpg.

Lol. Thanks for telling me.

NascentOxygen
Staff Emeritus
Seems there is a "+" sign missing in (4).

It should be t(n/2k) + n + n/2 + ....

Then in going from (5) to (6), make use of the fact that
n/2k-1 ≡ n/(2k/2)
≡ 2n/2k, but k=log2n
≡ 2n/n
≡ 2