Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 6 down vote favorite
1

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?

share|improve this question
Take a divide-and-conquer algorithm for sorting. – Nicholas Mancuso Nov 7 '12 at 23:37
3  
@NicholasMancuso: Divide and Conquer is not Dynamic programming, since the subproblems are non-overlapping. – A.Schulz Nov 8 '12 at 9:18
@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. – Raphael♦ Nov 9 '12 at 8:10

2 Answers

up vote 3 down vote

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.

share|improve this answer
up vote 1 down vote

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.

share|improve this answer
1  
I'm interested in a more nuanced definition of DP. In your example, there's no sub-problem overlap and no memoization required. – Joe Nov 8 '12 at 0:44
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. – Raphael♦ Nov 9 '12 at 8:08
DP naturally is bottom up but divide-and-conquer is in reverese (also this is not related to memoization). – Saeed Amiri Nov 9 '12 at 13:34
1  
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. ;) – Nicholas Mancuso Nov 9 '12 at 14:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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