What can be said about the time complexity of given Code snippet?

Question

fun(int n)
{
    if (n == 1)
       S1 // S1 takes O(N) time
    else 
       S2 + fun(n-1) // S2 takes O(1) time
}

What can be said about the time complexity of given Code snippet ?

---

I think the recurrence equation can be written as $T(N) = T(N-1) + N$ and this says Time complexity = $O(N^2)$

But I am not sure about this ?

Answer 1

It is linear in $N$. The recurrence is $T(n) = T(n-1)+C$ with $T(4)$ being a constant, since you do a constant amount of work (the if statement, and then the return) at each step before calling the recursion.