CODEWITHSUNDEEP
runtimerecurrencebig-o
maxicecil21
maxicecil21

Reputation: 11

Big theta running time of this recursive function

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?

Upvotes: 0

Views: 712

Answers (1)

Matt Ball
Matt Ball

Reputation: 359786

  • 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?

Upvotes: 1

Related Questions