# Time Complexity of a Memoized Algorithm

The memoization eliminated duplicate calls to a function. A memoized implementation of Fibonacci code is as follows:

``````package complexity

import "fmt"

var mem map[int]int

func fibo(count int) int {
if count == 0 || count == 1 {
return count
}

if mem[count] != -1 {
return mem[count]
}

s := fibo(count-1) + fibo(count-2)
mem[count] = s
return s
}

func Fibo(count int) {
mem = make(map[int]int, count)

for i := 0; i <= count; i++ {
mem[i] = -1
}

fmt.Printf("fibonacci number for count=%+v is %v\n", count, fibo(count))
fmt.Printf("fibonacci map is %v\n", mem)
}
``````
``````\$ go run main.go
fibonacci number for count=4 is 3
fibonacci map is map[0:-1 1:-1 2:1 3:2 4:3]
``````

Since each function in the recursion tree is processed at most once, the worst-case complexity of the above code becomes O(N).

Reference
https://stackoverflow.com/questions/42617249/time-complexity-of-memoization-fibonacci

Written with StackEdit.

This site uses Akismet to reduce spam. Learn how your comment data is processed.