Most of the classic examples of dynamic programming algorithms have run-times such as $n$ or $n^2$. Are there any natural examples with a $O(n \log n)$ run-time?

  • $\begingroup$ Take a divide-and-conquer algorithm for sorting. $\endgroup$ – Nicholas Mancuso Nov 7 '12 at 23:37
  • 4
    $\begingroup$ @NicholasMancuso: Divide and Conquer is not Dynamic programming, since the subproblems are non-overlapping. $\endgroup$ – A.Schulz Nov 8 '12 at 9:18
  • $\begingroup$ @A.Schulz Actually, they are. The same subsequence may appear in multiple branches of the the recurrence (I am thinking of the Mergesort recurrence). We ignore this during sorting because we don't need more speedup; the fact that we have to try only one partitioning for every input and find the optimal (sorted) solution dominates the effect. $\endgroup$ – Raphael Nov 9 '12 at 8:10

One natural example is finding the longest increasing subsequence of a sequence of $n$ numbers. Candidate subsequences can be linked in the input sequence. This is a fairly common exercise, and works for other type of subsequences, too. It is actually the exercise 15.4-6 in the 3rd edition of the Cormen et al. book too. For an algorithm, see Section 2.2 in these notes.


To expand on my comment:

While sorting is not doing a "table lookup", remember the actual definition of DP:

Method for solving problems that have optimal substructure.

We see that a divide-and-conquer approach for sorting satisfies this.

  • 1
    $\begingroup$ I'm interested in a more nuanced definition of DP. In your example, there's no sub-problem overlap and no memoization required. $\endgroup$ – Joe Nov 8 '12 at 0:44
  • $\begingroup$ As far as I know, there is no such thing as "the actual definition of DP". The termin "optimal substructure" is not very precise, too. Regarding the statement of your answer, if you extend the notion of DP to data transformation problems (usually only considered optimisation and decision problems are considered), I think it is reasonable to call, say, the Mergesort recurrence a DP recurrence. It's a very special case since we only have to try one partitioning, though. $\endgroup$ – Raphael Nov 9 '12 at 8:08
  • $\begingroup$ DP naturally is bottom up but divide-and-conquer is in reverese (also this is not related to memoization). $\endgroup$ – user742 Nov 9 '12 at 13:34
  • 1
    $\begingroup$ To everyone. I agree that divide and conquer doesn't really conform to the most typical form of DP. I've always felt it was a special case for technicality reasons (optimal substructure, ie Bellman's Principle of Optimality). But In light of Joe's comment, perhaps I should offer a more convincing example. ;) $\endgroup$ – Nicholas Mancuso Nov 9 '12 at 14:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.