0
int e(int x, int n)
{
  static int f=1, p=1; // f for factorial evaluation & p for power evaluation
  int r;

  if(n==0){
    return 1;
  }

  else {
    r = e(x, n-1);
    p = p*x;
    f = f*n;
    return r + p/f;
  }
}

void main(){
  // Just for example
  int n = 4;
  int x = 1;
  int r = e(1, 4);
}

Trying to find the Taylor series of e^x using recursion (involving static variables) Now, when we count the number of multiplications here, then mathematically we count it by writing the series and adding the total number of multiplications involved, which gives a total of n(n+1)/2 multiplications, i.e. O(n^2) multiplications and so is the time complexity

But if I try to count the number of multiplications by tracing this recursion, then I get 2*n - 1 multiplications, i.e. O(n) multiplications only,

So, now I'm starting to think that this happened because of the static variables. If I'm wrong by any means, then please explain me step by step to find the time complexity of this recursive function by tracing its recursion tree.

Ripi2
  • 7,031
  • 1
  • 17
  • 33
Deepak
  • 11
  • 6
  • I’m voting to close this question because it's based on an incorrect premise. – pjs Sep 01 '23 at 20:59
  • 1
    `static` variables are not changing time complexity they just behave like global variables however in recursive function they can alter space complexity and constant factor (just like using global variables) and also significantly lower heap thrashing which might give a major speedup (simply by moving recursive function operands into static variables) and also greatly improve max depth of recursion without stackoverflowing – Spektre Sep 02 '23 at 06:03
  • @pjs Why, please don't. Rather help me find the time complexity of the above code. Now, I'm really confused whether it is O(n) or O(n^2)? – Deepak Sep 02 '23 at 07:30
  • 1
    Calculate and write down the first 10 factorials by hand. (You may use a calculator). How many multiplications do you need? I need about 10. A computer program can do the same, with or without static variables. – n. m. could be an AI Sep 02 '23 at 15:23

2 Answers2

1

To say the result, there's nothing related with the static values. And your mathematically counting is wrong.

I have tried your code with python. This is the code what I have tried.

f = 1
p = 1
multi = 0

def e(x, n):
    global f
    global p
    global multi
    
    print('calling e', x, n)
    if n==0:
      return 1

    r = e(x, n-1)
    p = p*x
    f = f*n
    multi += 2 # there's 2 multiples
    print('multiply done', multi)
    return r + p/f

r = e(1, 4)

And I get this result.

calling e 1 4
calling e 1 3
calling e 1 2
calling e 1 1
calling e 1 0
multiply done 2
multiply done 4
multiply done 6
multiply done 8

As you see the result, the recursion is just called for n+1 times. The recursion tree is simple: It calls the params as (x, n-1), (x,n-2), ... (x,0). And at each call, the multiplications are not done n times. It is just done 2 times. So total count is 2*n times. Your mistake was that in every call the multiplication is done for n times (n - given parameter, not original n).

Coding Ninja
  • 84
  • 6
  • Ok, saw that mistake, so if only total multiplications are considered, then the count is 2n times, i.e. O(n), but if the time complexity is considered for the entire evaluation, including all statements, including the summation portion (i.e. the return and the calling statements as well), then it's count is (n+1)^2 + 2n multiplications, i.e. O(n^2). Please do look into this too, it is just that as soon as we change the work/statements we focus on, the complexity or big O value changes. – Deepak Sep 01 '23 at 20:09
  • 1
    Nope, there's no `for` or `while` statement in your `e` function, and the function is called for n times. So the complexity is O(n). Please tell me why you think the count is (n+1)^2. How did you calculate that? – Coding Ninja Sep 01 '23 at 20:44
  • Refer to this link https://www.geeksforgeeks.org/program-to-calculate-ex-by-recursion/ . Here they count the total number of multiplications in just the expanded definition of the e^x as per Taylor Series, then based on that they conclude the time complexity as O(n^2) since the total count is n(n+1). And I do the same from the code, by tracing it, then it finally comes as ( n+1)^2 + 2n multiplications (because consider all statements in the code). – Deepak Sep 02 '23 at 07:09
  • @Deepak you are reusing lowers powers that are "already" computed so `x^3 = x^2 * x` instead of `x^3 = x*x*x` which leads to `O(n)` ... – Spektre Sep 02 '23 at 14:32
1

I see O(N) time and some mistakes for example:

int n = 4;
int x = 1;
int r = e(1, 4);

should probably be:

int n = 4;
int x = 1;
int r = e(x, n);

or just:

int r = e(1, 4);

first for taylor I would expect the x to be floating point type (and all derived variables/stuff from it too) otherwise you got rounding to integer invalidating result...

Your e function does not init static variables so you can not use it more than once...

To remedy your code (putting all together) I would:

int e(float x, int n,bool init=true)
  {
  static float p;
  static int f;
  if (init){ f=1; p=1.0; }
  if(n==0) return 1;
  else 
    {
    p *= x;
    f *= n;
    return e(x, n-1,false) + p/float(f);
    }
}

void main()
  {
  // Just for example
  int n = 4;
  float x = 1;
  float r = e(x, n);
  }

well I would not use recursion for this at all really instead simple iteration loop would be much faster and clear see:

Spektre
  • 49,595
  • 11
  • 110
  • 380