On: MIT’s Introduction to Algorithms, Lecture 3: Divide and Conquer

[aston]

The killer concept to grok with divide-and-conquer is that it's only powerful if

  1) the smaller version of the problem is actually
     easier to solve and not just smaller
                  - or -
  2) the smaller version of the problem is just as 
     hard to solve, but you can combine smaller versions into
     a bigger one with less work than doing the bigger itself.

Quicksort is an example of the former (partitioning a list of size 2 or less is sorting it, even though partition is linear time). Merge sort is too (combining two sorted lists is linear time). Repeated squaring is an example of the latter, as is the Strassen matrix multiplication.

I took this class, and it took me a lot of just sitting around pondering before I got that stuff.

[pkrumins → aston]

Thanks for your insightful comment! Can I use it in my post? (full credit to you)

[aston → pkrumins]

Yeah, definitely.