Ramer–Douglas–Peucker algorithm: Difference between revisions

Revision as of 02:33, 17 July 2011

Revision as of 02:35, 17 July 2011

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, pathologicalthe casesworst can be devised for which thecase complexity is <math>O(n^2)</math>

==References==