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

#1 harro.rm  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • 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  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • 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
Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12177
  • View blog
  • Posts: 45,245
  • 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).
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1