CODEWITHSUNDEEP
dynamic-programming
arkham knight
arkham knight

Reputation: 383

Running time - Dynamic programming algorithm

Any dynamic programming algorithm that solves N sub problems in the process of computing it's final answer must run in Ω(N) time.

Is this statement true? I am thinking that it is indeed true as i need to compute every sub problem. Please let me know if i am wrong

Upvotes: 1

Views: 4429

Answers (1)

Boen Du
Boen Du

Reputation: 21

The short answer is no. Dynamic programming is more of a strategy to boost up performance/shorten runtime complexity than an actual algorithm. Without knowing the actual algorithm for a specific problem, it's not possible to say anything about time complexity.

The idea of DP is to use memoization(by consuming some space) to speed up exisiting algorithm. Moreover, every algorithm that you can apply DP may speed up in different ways. Without re-computing the same subtask multiple time, you will have to store intermediate results in another data structure. If the result is needed again in your data strucutre, you will directly return intermediate results you've stored

With that being said, the time complexity of DP problems is the number of unique states/subproblems * time taken per state.

Here's one example when DP solves N sub problems and computation is not Ω(N). let's assume your DP requires O(n) subproblems and evaluating each subproblem costs an O(logn) binary search plus constant time operations.

Then the overall algorithm would take O(n*logn).

Upvotes: 1

Related Questions