Finding Fibonacci number by dynamic programming - Algorithm

Question

I was reading the most voted answer from here: Difference between Divide and Conquer Algo and Dynamic Programming, but I don't have enough reputation to comment so I have to post a new question.

My question is: why is the overall time O(n)?

To my understanding, finding an element from an unsorted array of size n can cost time n.

And in the case of finding the fibonacci number, the worst case to check if a number is in memo could cost n time, so the whole algorithm will repeat n times, and each time it'll search for the number once, which costs n time. Then the overall time should be O(n^2) instead of O(n).

Could anybody point out where I misunderstood? Thanks

The Fibonacci numbers are not stored in an unordered array that you have to search. Fx is stored in memo[x], so it can be read in O(1). — m69's been on strike for years, Sep 15 '18 at 18:45

score 0 · Answer 1 · answered Sep 15 '18 at 20:04

0

Due to memoization the asymptotic complexity becomes O(n).

Searching of the memoized fibonacci is not O(n), It is O(1) considering you are using array not a LinkedList.

answered Sep 15 '18 at 20:04

Avishek Bhattacharya

6,534
3
34
53

Finding Fibonacci number by dynamic programming - Algorithm

1 Answers1