How can i find the time complexity of below function?

Question

Can anyone guide me to find the time complexity? Does the time complexity change over operating systems?

int fn(int n){
   if(n==1){
     return 1;
    }
    else{
     return(fn(n-1)+ fn(n-1));
    } 
}

Answer 1

You can make a recurrence relation T which represents the time it would take to compute and input of size N and then use the method of telescoping to help find the Big-O like so:

T(N) = T(N-1) + T(N-1) + c = 2*T(N-1) + c

Here, we can see that the time it will take to compute T(N) will be 2*T(N-1) plus a constant amount of time c. We can also see by your function that:

T(1) = b

Here, we can see by your base case that there are no recursive calls when N=1, so, it will take a constant time b to compute T(1).

If we take a look at T(N), we need to find out what T(N-1) is, so computing that we get:

T(N-1) = 2*T(N-2) + c

Computing T(N-2) we get:

T(N-2) = 2*T(N-3) + c

Thus, we can sub these back into each other...

T(N-1) = 2*(2*T(N-3) + c) + c = 4*T(N-3) + 3c

T(N) = 2*(4*T(N-3) + 3c) + c = 8*T(N-3) + 7c

By looking at the pattern produced by stepping down into our equation, we can generalize it in terms of k:

T(N) = 2^k * T(N-k) + ((2^k)-1 * c)

We know that our recursive calls will stop when T(N-k) = T(1), so we want to find when N-k = 1, which is when k = N-1, so subbing in our value of k and removing the constant-variable times, we can find our Big-O:

T(N) = (2^N) * T(1) + (2^N)-1 * c
= (2^N) * b + (2^N)-1*c
= O(2^N)     (-1, b & c are constants, so they can be removed, giving 2*(2^N), where 2* is a constant, giving 2^N)

Time complexity is a measurement of how well an algorithm will scale in terms of input size, not necessarily a measure of how fast it will run. Thus, time-complexity is not dependent on your operating system.

Answer 2

The function is a recursive function (it calls itself). In that case, its time complexity is either linear or exponential (or something else, which we won't cover here):

It is linear, if you can do TCO (tail call optimization), or in other words, turn the function into a loop:

  int loop(int i, int count) {
    if(i > 10) return count;
    return loop(i - 1, count + 1);
 }

 loop(0, 0);

 // can be turned into
 int count = 0;
 for(int i = 0; i <= 10; i++) {
   count = count + 1;
 }

Otherwise, it is exponential, as every call will execute the function again m times, and each of those m calls, calls the function again m time and so on. This will happen until the depth n is reached, so the time complexity is:

 O(m ^ n)

Now m is kind of a constant, as the number of recursive calls doesn't change (it's two in your case), however n can be changed. Therefore the function has exponential time complexity. That's generally bad, as exponential numbers get really large for relatively small datasets. In your case however, it is trivial to optimize. a + a is the same as a * 2, thus your code can be turned into:

int fn(int n){
   if(n==1){
        return 1;
    }  else {
       return fn(n - 1) * 2;
    } 
 }

And that is .... linear!

Does the time complexity change over operating systems?

No, the time complexity is an abstract concept, it doesn't depend on the computer, operating system, language,... You can even run it on an automaton.

when n=1, the time complexity is 1...

No! n is not a constant. n is part of the input, and time complexity is a way to estimate the time depending on the input.

Answer 3

Here is the approach I would take.

from the function definition we can deduce that

O(f(n)) = c + 2 * O(f(n-1))

If we ignore constant terms

O(f(n)) = 2 * (2 * f(n-2))

so we can say the complexity here is O(2^n)