CODEWITHSUNDEEP
pythonbig-o
heretoinfinity
heretoinfinity

Reputation: 1746

Fibonacci sequence time and space complexity

This is not the most efficient way to get Fibonacci sequence numbers but I am learning Big O and would like confirmation and explanation of the space and time efficiency of the code below. The code is in Python and I wrote it such that I use a list and append to it and just return the last value.

The append method takes O(1) time as shown here but I am doing the operation almost n times so would I get O(n) for time complexity?

With regard to space complexity, should I consider the space used as an arithmetic series because the list would have to be moved elsewhere if the number entered is larger than what is given to the function stack at the beginning?

The code in this question is for the recursive approach.

def getFib(position):
  if position == 0:
    return 0
  if position == 1:
    return 1

  list_ = [0, 1]
  previous = 1

  for pos in range(2, position+1):
    list_.append(list_[pos-1] + list_[pos-2])

  return list_[position]

if __name__ == "__main__":
  print(getFib(0))
  print(getFib(1))
  print(getFib(2))
  print(getFib(3))
  print(getFib(4))
  print(getFib(5))
  print(getFib(6))
  print(getFib(7))
  print(getFib(8))
  print(getFib(9))

Upvotes: 0

Views: 567

Answers (1)

Maxime Chéramy
Maxime Chéramy

Reputation: 18851

time complexity: O(n) because you are executing n times your loop that has a constant time complexity.

space complexity: O(n) because you are storing n numbers in your list.

Of course, you didn't need to store all the numbers but only the last two values. That would have reduced the space complexity to O(1).

Upvotes: 1

Related Questions