7

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!

3 Answers 3

21

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)

2
  • @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?
    – user1174868
    Feb 21, 2015 at 18:54
  • @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.
    – Brian
    Jan 30, 2016 at 23:55
3

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).

0

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.