Revision as of 02:42, 17 July 2011 edit 71.164.79.232 (talk) →Complexity ← Previous edit		Revision as of 02:42, 17 July 2011 edit undo 71.164.79.232 (talk) →Complexity Next edit →
Line 52: == Complexity == The expected complexity of this algorithm can be described by the linear recurrence <math>T(n) = 2T\left(\frac{n}{2}\right) + O(n)</math>, which has the well-known solution (via the [[Master Theorem]]) of <math>T(n) \in \Theta(n\log n)</math>. However, the worst case complexity is <math>O\left(n^2\right)</math>. ==References==

Ramer–Douglas–Peucker algorithm: Difference between revisions