Recurrence Relation: Solving Big O of T(n-1)

big-o recurrence
Parth picture Parth · Jul 11, 2010 · Viewed 32.8k times · Source

I'm solving some recurrence relation problems for Big O and so far up till this point have only encountered recurrence relations that involved this form:

T(n) = a*T(n/b) + f(n)

For the above, it's quite easy for me to find the Big O notation. But I was recently thrown a curve ball with the following equation:

T(n) = T(n-1) + 2

I'm not really sure how to go around solving this for Big O. I've actually tried plugging in the equation as what follows:

T(n) = T(n-1) + 2
T(n-1) = T(n-2)
T(n-2) = T(n-3)

I'm not entirely sure if this is correct, but I'm stuck and need some help. Thanks!

Answer

Andreas Jansson picture Andreas Jansson · Jul 11, 2010

Assuming T(1) = 0

T(n) = T(n-1) + 2
 = (T(n-2) + 2) + 2
 = T(n-2) + 4
 = (T(n-3) + 2) + 4
 = T(n-3) + 6
 = T(n-k) + 2k

Set k to n-1 and you have

T(n) = 2n - 2

Hence, it's O(n)

Related questions

Solving the recurrence relation T(n) = √n T(√n) + n

Is it possible to solve the recurrence relation T(n) = √n T(√n) + n Using the Master Theorem? It is not of the form T(n) = a ⋅ T(n / b) + f(n) but this problem is given in the exercise …

Read More
Reccurrence T(n) = T(n^(1/2)) + 1

I've been looking at this reccurrence and wanted to check if I was taking the right approach. T(n) = T(n^(1/2)) + 1 = T(n^(1/4)) + 1 + 1 = T(n^(1/8)) + 1 + 1 + 1 ... = 1 + 1 + 1 + ... + 1 (a total of rad n times) = n^(1/2) So the answer would come to theta bound …

Read More
Solving a recurrence T(n) = 2T(n/2) + n^4

I am studying using the MIT Courseware and the CLRS book Introduction to Algorithms. I am currently trying to solve the recurrence (from page 107) T(n) = 2T(n/2) + n4 If I make a recurrence tree, I get: Level 0: n4 Level 1 2(…

Read More