complexities

Question 1

fibonacci dynamic programming complexity

Answer 1

time: O(n)

Question 2

matrix chain multiplication – DP

Answer 2

time: O(n^3)

Question 3

knapsack – DP

Answer 3

time: O(nW), number of items * max_weight
space: also O(nW)

Question 4

longest common subsequence – dp

Answer 4

O(nm), length of first string * length of second string