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.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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

%d bloggers like this: