Fibonacci sequence time and space complexity

Question

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))

This is O(n) Time and Space Complexity? You are doing a `for` loop from `0 to n`. Each time a new item is added. — Nishant, Apr 14 '18 at 14:56
You have a loop that takes `position` steps and create a list of size `position`. Seems pretty straightforward. — President James K. Polk, Apr 14 '18 at 14:58

score 1 · Accepted Answer · answered Apr 14 '18 at 14:59

1

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).

answered Apr 14 '18 at 14:59

Maxime Chéramy

17,761
8
54
75

Is it O(n) because you are considered amortized analysis as shown here where O(3n) simplifies to O(n)? https://www.interviewcake.com/concept/java/dynamic-array-amortized-analysis – heretoinfinity Apr 15 '18 at 18:21
1

Yes, I used as assumption that `append` is constant in time (O(1)). – Maxime Chéramy Apr 16 '18 at 07:02

Fibonacci sequence time and space complexity

1 Answers1