CODEWITHSUNDEEP
timetime-complexitycomplexity-theory
user11317524
user11317524

Reputation:

TimeComplexity : O(n) VS O(2^n)

Given the following two functions, why is the time complexity of the first n while the second is 2^n?

The only difference is the +1 before the return in the second function. I don't see how that can influence the time complexity.

int f1(int n){

   if (n==1)
    return 1;

  return f1(f1(n-1));


}

int f2(int n){

   if (n==1)
    return 1;

  return 1+f2(f2(n-1));


}

Upvotes: 4

Views: 319

Answers (2)

jwezorek
jwezorek

Reputation: 9545

The key insight here is that f1 always returns one, given anything, and f1(1) is evaluated in constant time.

Each of these functions will result in two recursive calls -- an inner recursive call first then an outer recursive call -- except in the case in which n is one. In that case the function will evaluate zero recursive calls.

However, since function f1 always returns 1 regardless of its input, one of the recursive calls it makes, the outer recursive call, will always be called on n of 1. Thus the time complexity of f1 reduces to the time complexity of f(n) = f(n-1) which is O(n) -- because the only other call it will make takes O(1) time.

When evaluating f2 on the other hand, the inner recursive call will be called on n-1 and the outer recursive call will be called on n-1 as well because f2(n) yields n. You can see this by induction. By definition, f2 of 1 is 1. Assume f2(n) = n. Then by definition f2(n+1) yields 1 + f2(f2(n+1-1)) which reduces to 1 + (n+1-1) or just n+1, by the induction hypothesis.

Thus each call to f2(n) results in two times however many calls f2(n-1) makes. This implies a O(2^n) time complexity.

Upvotes: 6

jpnadas
jpnadas

Reputation: 773

It is related to the time it would take for the recursive function to return.

In the first function, the 1 that you return is carried outside of all of them, and so when you reach 1, you immediately end all nested calls.

On the second function, because the return is incremented by 1, when you reach 1, you create more nested calls.

To visualize this, put a print statement in your function and examine the output.

In python, that would be

def f1 (n):
    print (n)
    if n < 2:
        return 1

    return f1(f1(n-1))

def f2 (n):
    print (n)
    if n < 2:
        return 1

    return 1 + f2(f2(n-1))

f1(10)
f2(10)

Upvotes: 0

Related Questions