Finding time complexity using recurrence relations

Question

I have a recurrence relation as follows:

U(n) = 3 when n = 3
U(n+1) = U(n) + n when n > 3

i.e

n   = 3   4   5   6   7
U(n)= 3   6  10  15  21

What would the time complexity of this be?

Answer 1

As a hint, if you unroll the recurrence, you'll see that it evaluates to

U(n) = (n - 1) + (n - 2) + ... + 3

Also, it might help to know that if you evaluate n(n + 1) / 2 (the sum of the first n positive natural numbers), you get back the sequence 0, 1, 3, 6, 10, 15, 21, etc. You can formalize the result by using a proof by induction.

Hope this helps!

Answer 2

Using recurrence relation you can obtain a formal closed form and the order of growth complexity: