time-complexitybig-odynamic-programmingfibonaccibiginteger# Time complexity of this dynamic programming algorithm to get nth fibonacci number

I'm confused about the time complexity of this algorithm:

```
function fib(n)
if n = 0
return 0
else
var previousFib := 0, currentFib := 1
repeat n โ 1 times // loop is skipped if n = 1
var newFib := previousFib + currentFib
previousFib := currentFib
currentFib := newFib
return currentFib
```

My intuition was that this algorithm takes O(n^{2}) time with O(n) space. But according to this wikipedia page, the time complexity is O(n) and the space is O(1). My reasoning was that `previousFib + currentFib`

gets very expensive very quickly. Specifically, if the size of `previousFib`

and `currentFib`

grows linearly with n, then shouldn't they both constitute O(n) space, and shouldn't `previousFib + currentFib`

constitute an O(n) operation?

Solution

There are different models for computational complexity. As Wikipedia - Computational complexity states:

The number of arithmetic operations is another resource that is commonly used. In this case, one talks of arithmetic complexity. If one knows an upper bound on the size of the binary representation of the numbers that occur during a computation, the time complexity is generally the product of the arithmetic complexity by a constant factor.

For many algorithms the size of the integers that are used during a computation is not bounded, and it is not realistic to consider that arithmetic operations take a constant time. Therefore, the time complexity, generally called bit complexity in this context, may be much larger than the arithmetic complexity.

This can be a source of confusion, more so because different models are used in different Wikipedia articles without really being specific on the model they used.

The Wikipedia article you referenced uses the first (*arithmetic* complexity) model, where it is assumed that arithmetic operations like addition happen in constant time as the involved integers are assumed to be stored in fixed size memory (like 64-bit integers).

You are correct in your analysis that Fibonacci numbers grow quickly: soon enough the fixed-size integer model will not be able to cope with these. For instance, an unsigned 64-bit representation can only hold up to ๐น_{93}. As Fibonacci numbers grow that quickly (having O(๐) bits) it only seems fair and practical to use the second (*bit* complexity) model, where an implementation would use a dynamic "big" integer type (like for instance Python offers out of the box). With those, arithmetic operations do not take constant time. Addition then has a O(๐) time complexity (where ๐ is the index of the Fibonacci number), as you rightly put it.

- How do I optimize this XOR sum algorithm?
- Find minimum cost to buy products
- FloydโRivest vs. Introselect algorithm performance
- Unexpected Invalid Memory Access in Recursive Function for Unique Number Search in CodeWars Challenge
- Find the number of valid substrings
- Time Complexity of Backtracking solution - Leetcode 473. Matchsticks to Square
- Can we get a better complexity than O(n) for cumulative sum while using multithreading?
- What is a plain English explanation of "Big O" notation?
- What's the time complexity of array.splice() in Google Chrome?
- Is lseek() O(1) complexity?
- O(n log n) algorithm to find number of large inversions
- How to analyze time complexity of an algorithm with different running time
- Minimum number of operations for array of numbers to all equal one number
- Time Complexities n(log(n)) and log(n^n)
- Find longest substring
- Fish codility excercise
- Is finding the largest cycle on a directed graph with 133 Nodes and 737 Edges Computable?
- Two implementation methods of BFS for finding the shortest path, which one is the obvious winner?
- Time complexity of this dynamic programming algorithm to get nth fibonacci number
- i stuck in leetcode problem 151. Reverse Words in a String
- Select by O(1) from SQL table
- Breadth First Search time complexity analysis
- Given a list and range, find sum based on new list in less time
- Optimal solution for the "celebrity" algorithm
- how can calculate time complexity of selection sort step by step?
- Find the highest amount of money a shopkeeper can make through a certain number of sales
- Algorithmic complexity to convert a set to a list in python
- Understanding Time Complexity of Geometric Progression Series
- Python string comparisons time complexity
- When can an algorithm have square root(n) time complexity?