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

Question

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!

Shorthanded

Answer 1

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)

Footboard

@AndreasJansson I do not follow your algebra on the first two steps. You claim that $T(n-1) + 2 = (T(n-2) + 2) + 2$ but I do not see how you come to this conclusion. Nothing in the problem hints at this so how can you make this assumption? What if $T(2) = 10000000000000000$ we don't know so how can you assume that it isn't? – Mccowan

@ripDaddy69 If we plug in (n-1) into the original T(n) we get, T(n-1) = T(n-2) + 2. Right? Now if we replace T(n-1) on the first line with T(n-2)+2 we get the second line. – Nonanonage

Answer 2

Since the question is already answered, let me add some intuition behind how to find the complexity of the recurrence.

• Master theorem applies only to the divide and conquer type recurrences, like T(n) = a*T(n/b) + f(n) where a is the number of subproblems and each of these subproblem's size is 1/b of the original problem. But recurrence T(n) = T(n-1) + 2 does not technically "divide" the problem into subproblems. so master theorem does not apply here.
• If we closely look at the recurrence, it is pretty clear that it goes over n steps and each step takes constant time, which is 2 in this case. So the complexity would be O(n).

I especially found the second intuition very helpful for most of the recurrences (may be not all). As an example, you can try the same for a similar recurrence T(n) = T(n-1) + n, for which the complexity is, of course, O(n^2).

Theoretician

Answer 3

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

So T(n) = 2*n which implies O(n)

Spigot