Compared to dynamic programming, greedy algorithms are
Aalways slower because they explore more states
Balways equivalent in output but slightly different in code
Cfaster (no memo table) but only correct with the greedy-choice property
Dslower per step but correct on more problems
Answer & Solution
Correct answer: C. faster (no memo table) but only correct with the greedy-choice property
Greedy skips the memo table that DP maintains, which makes it faster. But it commits irrevocably to local choices, so it only works on problems where the locally best choice is globally safe. DP handles more problems (anything with optimal substructure); greedy handles fewer but with less overhead.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for