runtime - Big theta running time of this recursive function

Question

I need a little help on figuring out the Big-Theta running time for this function.

int recursive(int n) {

    sum = 0;
    for (int i = 1; i <= n; i++)
        sum++
    if (n > 1)
        return sum + recursive(n-1);
    else
        return n;
}

I know how what the run time of this function would be if the for loop wasn't in the function, but the loop is throwing me off a little bit. Any advice?

Answer 1

• If it was just the for loop, not recursive, the function would be O(n).
• If it was just recursive, and didn't have the for loop, it would also be O(n).
• But, it's doing n recursive steps (which we know is O(n)) and it's got an O(n) for loop at each of the n steps.

So... does that help?