# Recurrence homework

Page 1 of 1

## 2 Replies - 1429 Views - Last Post: 01 July 2016 - 08:17 PM

### #1 harro.rm

Reputation: 0
• Posts: 63
• Joined: 18-June 16

# Recurrence homework

Posted 01 July 2016 - 07:42 PM

I'm a bit confused with solving recurrences.
E.g: T(n) = T(n - 2) + 4

I can't use the master theorem for this, so how would the iterative method work?
Is This A Good Question/Topic? 0

## Replies To: Recurrence homework

### #2 harro.rm

Reputation: 0
• Posts: 63
• Joined: 18-June 16

## Re: Recurrence homework

Posted 01 July 2016 - 08:01 PM

Hmm, there's no edit button. So hope it is okay for me to post again.
Is my calculation correct:

T(n) = T(n - 2) + 4
. T(n - 2) = T(n - 2 - 2) + 4 = T(n - 4) + 4
T(n) = T(n - 4) + 4 + 4 = T(n - 4) + 8
. T(n - 4) = T(n - 4 - 2) + 4 = T(n - 6) + 4
T(n) = T(n - 6) + 4 + 8 = T(n - 6) + 12

General form: T(n) = T(n - k) * k
Let k = n - 1 = T(n - (n - 1)) = T(1)
T(n) = T(n - (n - 1)) * (n - 1)
T(n) = T(1) * (n - 1)
T(n) = n

### #3 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12226
• Posts: 45,301
• Joined: 27-December 08

## Re: Recurrence homework

Posted 01 July 2016 - 08:17 PM

Moved to Computer Science.

Take the sum from i = 0 to n/2 of 4 = 4 * n/2 = 2n = O(n).