Search code examples
recurrence

Write Recurrence for Given Function

I am trying to write the recurrence relation for the running time of the following function:

function G(n):
    if n>0 then:
        x=0
        for i = 1 to n:
            x = x + 1
         G(n-1)
    end if

What I came up with was:

 T(n) = 1 if n <= 0
 T(n) = T(n-1) + 1 if n>0

However I was told that this was incorrect and I don't know why or what the correct solution would be. Any help is greatly appreciated!

Solution 
  • T(n) = 1 if n <= 0
T(n) = T(n-1) + O(n) if n>0

    Instead of O(1), it should be O(n), because you are looping from 1 to n

    If you solve the recurrence, the overall complexity will be O(n2)