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
– Nishant, Commented Apr 14, 2018 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
– President James K. Polk, Commented Apr 14, 2018 at 14:58

Maxime Chéramy · Accepted Answer · 2018-04-14 14:59:16Z

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, 2018 at 14:59

Maxime Chéramy

19k10 gold badges58 silver badges77 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

heretoinfinity Over a year ago

Is it O(n) because you are considered amortized analysis as shown here where O(3n) simplifies to O(n)? interviewcake.com/concept/java/dynamic-array-amortized-analysis

Maxime Chéramy Over a year ago

Yes, I used as assumption that append is constant in time (O(1)).

Collectives™ on Stack Overflow

Fibonacci sequence time and space complexity

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related