title: Fibonacci: Time Complexity and Big O Notation
body: <p>I have seen several solution of Fibonacci from different tutorials site and one thing that I noticed is that they have the same way of solving the problem through recursive function. I tested the recursive function and it takes 77 seconds before I get the 40th item in the list so I tried to make a function without dealing recursive function through a for loop and it only takes less than a second. Did I made it right? What is the O notation of my function?</p>
  
  <pre><code>from time import time
  
  
  def my_fibo(n):
      temp = [0, 1]
      for _ in range(n):
          temp.append(temp[-1] + temp[-2])
      return temp[n]
  
  
  start = time()
  print(my_fibo(40), f'Time: {time() - start}')
  # 102334155 Time: 0.0
  </code></pre>
  
  <p>vs</p>
  
  <pre><code>from time import time
  def recur_fibo(n):
      if n &lt;= 1:
          return n
      else:
          return recur_fibo(n - 1) + recur_fibo(n - 2)
  
  
  start = time()
  print(recur_fibo(40), f'Time: {time() - start}')
  # 102334155 Time: 77.78924512863159
  </code></pre>