My sum all Odd Fibonacci numbers runs very slowly

My sum all Odd Fibonacci numbers runs very slowly. Is there room for optimization?

function sumFibs(num) {
  var sum = 0;
  
  var i = 1;
  while(fib(i) <= num){
    if(fib(i) % 2 == 1){
      sum+=fib(i);
     }
   i++;
  }
  
  return sum;
}

function fib(n){
  if(n==1 | n==2){
     return 1;
  } else {
     return fib(n-2) + fib(n-1);
  }
}

sumFibs(4);

it looks like your recalculating the value of fib (i) for every iteration of the loop which is something on the order of n^2 time. (i’m not an optimization expert, that’s just a guess. mabye even 2n^2 because you check fib(i) twice.

If instead you created a fibonacci set of numbers once to start with, then you can manipuliate it and it will be an order of 2n instead.

1 Like