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

  • Thread starter s3a
  • Start date
  • #1
s3a
800
8

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!
Thanks in advance!
 

Attachments

Last edited:

Answers and Replies

  • #2
280
0

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!
Thanks in advance!
You forgot to attach Problem.jpg.
 
  • #3
s3a
800
8
Lol. Thanks for telling me.
 
  • #4
NascentOxygen
Staff Emeritus
Science Advisor
9,244
1,072
Seems there is a "+" sign missing in (4).
koZTB.gif


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 
 

Related Threads on Solve the recurrence: t(n) = t(n/2) + n + 2 (Solution included).

  • Last Post
Replies
8
Views
676
  • Last Post
Replies
5
Views
655
  • Last Post
Replies
8
Views
732
Replies
1
Views
5K
  • Last Post
Replies
6
Views
2K
Replies
8
Views
2K
Replies
6
Views
1K
Replies
4
Views
1K
  • Last Post
Replies
5
Views
824
Replies
13
Views
791
Top