title: Codility FibFrog Algorithm - Improving Time Complexity from O(N * log(N) ** N) to O(N*log(N))
body: <p>I'm trying to solve the Codility <a href="https://app.codility.com/programmers/lessons/13-fibonacci_numbers/fib_frog/" rel="nofollow noreferrer">FibFrog</a> problem and I came up with the following solution:</p>
  <pre><code>def jumps_from(position, fb, A): 
      paths = set([])
      for i in fb: 
          newPos = position + i
          if newPos == len(A):
              return set([-1])
          elif newPos &lt; len(A):
              if A[newPos] == 1: 
                  paths.add(newPos)
          else: break
      return paths
              
  def solution(A):
      if len(A) &lt; 3: return 1 
      fibonaccis = fibonacci(len(A))
      if len(A) + 1 in fibonaccis: return 1
      paths = set([-1])
      steps = 0
      while True:
          paths = set([idx for pos in paths for idx in jumps_from(pos, fibonaccis, A)])
          if len(paths) == 0: return -1
          if -1 in paths: 
              return steps + 1
          steps += 1
      return steps 
  
  def fibonacci(N): 
      arr = [0] * (N + 2)
      arr[1] = 1
      for i in range(2, N + 2): 
          arr[i] = arr[i-1] + arr[i-2]
      return dict.fromkeys(arr[2:], 1)
  </code></pre>
  <p>Codility detects the runtime of this as <code>O(N * log(N) ** N)</code>.</p>
  <p>Codility Report: <a href="https://app.codility.com/demo/results/trainingJV7YAC-G3B/" rel="nofollow noreferrer">https://app.codility.com/demo/results/trainingJV7YAC-G3B/</a></p>
  <p>I'm comparing this with the following <a href="https://stackoverflow.com/a/64558623/8677071">solution</a>, which scores 100% on Codility, and has runtime <code>O(N * log(N))</code>:</p>
  <pre><code>def gen_fib(n):
      fn = [0,1]
      i = 2
      s = 2
      while s &lt; n:
          s = fn[i-2] + fn[i-1]
          fn.append(s)
          i+=1
      return fn
  
  def new_paths(A, n, last_pos, fn):
      &quot;&quot;&quot;
      Given an array A of len n.
      From index last_pos which numbers in fn jump to a leaf?
      returns list: set of indexes with leaves.
      &quot;&quot;&quot;
      paths = []
      for f in fn:
          new_pos = last_pos + f
          if new_pos == n or (new_pos &lt; n and A[new_pos]):
              paths.append(new_pos)
      return paths
  
  
  def solution(A):
      n = len(A)
      if n &lt; 3:
          return 1
  
      # A.append(1) # mark final jump
      fn = sorted(gen_fib(100000)[2:]) # Fib numbers with 0, 1, 1, 2..  clipped to just 1, 2..
      # print(fn)
      paths = set([-1]) # locate all the leaves that are one fib jump from the start position.
  
      jump = 1
      while True:
          # Considering each of the previous jump positions - How many leaves from there are one fib jump away
          paths =  set([idx for pos in paths for idx in new_paths(A, n, pos, fn)])
  
          # no new jumps means game over!
          if not paths:
              break
  
          # If there was a result in the new jumps record that
          if n in paths:
              return jump
              
          jump += 1
  
      return -1
  </code></pre>
  <p>I'm not sure why my solution differs in runtime, since the approach is exactly the same - compute all the indices you can jump to from <code>-1</code>, and then compute all the indices you can jump to from the new positions, until you get to the other side of the river, or no new positions can be found.</p>