CODEWITHSUNDEEP
mathbig-o
Mohamed Salah
Mohamed Salah

Reputation: 975

How to calculate the complexity of time and memory

I have the following code 

public int X(int n)
{
    if (n == 0)
        return 0;

    if (n == 1)
        return 1;
    else
        return (X(n- 1) + X(n- 2));
}

I want to calculate the complexity of time and memory of this code

My code consists of a constant checking if (n == 0) return 0; so this will take a constant time assume c so we have either c or c or the calculation of the recursion functions which I can't calculate

Can anyone help me in this?

Upvotes: 0

Views: 54

Answers (1)

Karthik
Karthik

Reputation: 5040

To calculate the value of X(n), you are calculating X(n-1) and X(n-2)

   So T(n) = T(n-1) + T(n-2);

      T(0) = 1
      T(1) = 1

which is exponential O(2^n)

If you want detailed proof of how it will be O(2^n), check here.

Space complexity is linear.

(Just to be precise, If you consider the stack space taken for recursion, it's O(n))

Upvotes: 1

Related Questions