2,300 views
0 votes
0 votes

Which of the following statement(s) is/are correct?
P: For a dynamic programming algorithm, computing all values in a bottom-up fashion is asymptotically faster than using recursion
Q: The running time of a dynamic programming algorithm is always Θ(P) where P is the number of sub-problems.( Marks: -0.66 )

I mark only P is true.

Answer neither P and Q

2 Answers

5 votes
5 votes
In case of DP memoization can be done at the same time complexity as bottom-up method. It's just looking at the same problem in two ways.

For a DP problem the complexity of solving the problem is given as: (#sub problems* cost of solving one subproblem).
0 votes
0 votes

P: False. A bottom-up implementation must go through all of the subproblems and spend the time per subproblem for each. Using recursion and memoization only spends time on the subproblems that it needs. In fact, the reverse may be true: using recursion and memoization may be asymptotically faster than a bottom-up implementation.

Q: False. The running time of a dynamic program is the number of subproblems times the time per subproblem. This would only be true if the time per subproblem is O(1).

Related questions