Dynamic programming

Question

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

Comments

Top down approach of dynamic programming meas recursion in this context.I think you rae confusing recursion with naive solution(Non DP sol)

---

yes you got me, thanks for reply.

In statement P if I am assume recursion as pure recursion without any Memoization then it is correct but if you say recursion with memoization then it is false.

---

This is what question means i guess. Dont worry,gate will mention things clearly if it comes:)

Answer 1

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).

Comments

But according to this article of GeeksForGeeks:

https://www.geeksforgeeks.org/dynamic-programming-set-1/

Time taken by Recursion method is much more than the two Dynamic Programming techniques mentioned above – Memoization and Tabulation!

Isn't this in total contradiction to your statement "In case of DP memorization can be done at the same time complexity as bottom-up method. It's just looking at the same problem in two ways. " 

---

asymptotically faster

That's the word you have to look at. 

Answer 2

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).