title: Time complexity of finding the Fibonacci index for a given n
body: <p>This is a bit hard for me to verbalize, but I'm curious to know how to calculate the time complexity of iterating <code>Fib(n)</code> times.</p>
  
  <p>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 <code>Fib(n) &gt; input</code>.</p>
  
  <p>The time complexity of the code is obviously <code>Fib(n)</code> but how to express that in Big-O notation?</p>
  
  <p>I've read this on <a href="https://math.stackexchange.com/questions/1972748/log-fibonacci-equals-to-theta">math exchange</a> which if I understand correctly says that the time complexity is <code>O(n log phi)</code> or about <code>O(1.618n)</code>. So <code>O(n)</code>?</p>
  
  <p>That feels wrong though.</p>
  
  <p>I've also found this other ressource for (Fibonacci formulas)[<a href="http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html#section6]" rel="nofollow noreferrer">http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html#section6]</a> and this one seems to say that it's actually:</p>
  
  <p><code>i ≈ log( N ) + (log(5) / 2) / log(Phi)</code></p>
  
  <p>The above feel like it makes more sense.</p>
  
  <pre><code> 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 &gt; 0) {
        int tmp = previous;
        previous = next;
        next = next + tmp;
  
        input -= next;
        if (input &gt;= 0) {
          count++;
        }
      }
  
      return count;
    }
  </code></pre>