0

This is a bit hard for me to verbalize, but I'm curious to know how to calculate the time complexity of iterating Fib(n) times.

I have the piece of code below that will iterate through the Fibonacci numbers and subtract that amount from a given input. The loop will run n times, where n is Fib(n) > input.

The time complexity of the code is obviously Fib(n) but how to express that in Big-O notation?

I've read this on math exchange which if I understand correctly says that the time complexity is O(n log phi) or about O(1.618n). So O(n)?

That feels wrong though.

I've also found this other ressource for (Fibonacci formulas)[http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html#section6] and this one seems to say that it's actually:

i ≈ log( N ) + (log(5) / 2) / log(Phi)

The above feel like it makes more sense.

 public int findTheMaximumUsingALoop(int input) {
    if (input == 1 || input == 2) {
      return input;
    }

    int count = 2;

    int next = 1;
    int previous = 1;

    input -= next + previous;

    // loop until the next Fib number is more than we have left
    while (input > 0) {
      int tmp = previous;
      previous = next;
      next = next + tmp;

      input -= next;
      if (input >= 0) {
        count++;
      }
    }

    return count;
  }
totsubo
  • 323
  • 4
  • 17

1 Answers1

2

That math exchange link is talking about the asymptotic behavior of log(Fib(n)) not Fib(n) so is not relevant.

Iterating Fib(n) times is exponential running time. You can see this by looking at the closed form formula for the nth Fibonacci number: (called Binet's formula)

enter image description here

which grows like O(phi ^ n) where phi is (1 + sqrt(5))/2, approximately 1.618.

However, the loop in your question will not iterate O(Fibo(n)) times. It will iterate O(n) times. It has the running time of calculating the nth fibonacci number via iteration.

jwezorek
  • 8,592
  • 1
  • 29
  • 46
  • thank you for the explanation. Thinking about what you wrote made me realize that my question is equivalent to asking what the complexity of calculating Fib(n) is. This other stackexchange post, [Computational complexity of Fibonacci Sequence](https://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence?rq=1) also helped – totsubo Oct 30 '19 at 00:12