0
$\begingroup$

I am analyzing the time complexity of the Douglas-Peucker line simplification algorithm. Reading online I've found that it has a worst-case running time of $O(n^2)$ where $n$ is the number of points on the line. However, I haven't been able to provide complete proof. Here is the pseudo-code I am working with:

pseudo-code

Here is my analysis:

Line 1: $O(1)$

Line 2: We can say that it goes through all points in the polyline formed by the first point and the last point in $PL$ and return the point with the maximum distance to the straight line between the mentioned points. We can safely say this is $O(n)$

Lines 4-6: If we are here we are doing two recursive calls. The number of elements used in each call could be different (not always in half). Depends on the point found in Line 2. Leaving implementation details aside, we can say that splitting is $O(1)$. Also, we have a $JOIN$ operation which would take $O(n)$ to join both lists.

Line 8: This is also a $JOIN$ operation but this only takes $O(1)$.

After looking at these steps I think we have the following recurrence relation:

$T(n) = T(index + 1) + T(n - index) + 2n$ where $index \in \{1, \dots, n-1\}$

Am I right? If so, how could I prove this is $O(n^2)$? Master Theorem?

Thank you very much in advance

EDIT: Changed description on Lines 4-6. Thus, also changed recurrence formula.

$\endgroup$
1
$\begingroup$

Your analysis seems correct, except for that you need $T(n)=T(index)+T(n-index+1)+2n$ instead because when $index$ is either $0$ or $n-1$ you won't get in the right hand side another factor of $T(n)$, which is not allowed.

In fact, it will yield something very close to the recurrence of the running time in the quicksort algorithm.

Worst case scenario

When index is either $0$ or $n-1$, the recurrence will boil down to $T(n)=T(1)+T(n-1)+2n = T(n-1) + (2n + T(1))$. You can easily show by induction that $T(n)=\Theta(n^2)$ in this case.

Best case scenario

We assume the input in the recursion will always be cut down by half. That is, the recursion is $T(n)=2T(n/2)+2n$.

Define $b=a=2$ and $f(n)=2n$. Then, $T(n)=aT(n/b)+f(n)$.

We can calculate $c_{crit}=\log_{b}(a)=\log_2(2)=1$ and thus $f(n)=2n=\Theta(n)=\Theta(n^{c_{crit}})$.

Now we can directly use the second case to get that $T(n)=\Theta(n^{c_{crit}}\log(n))=\Theta(n\log(n))=O(n^2)$

Average case scenario

If we assume that the input is a random variable, such that the choice of $index$ is uniformly distributed in $\{0,\dots,n-1\}$, then the algorithm takes expected time $\Theta(n\log(n))$. Take a look at the proof for quicksort to see how its done.

$\endgroup$
4
  • $\begingroup$ Thanks for answering, does this means that $O(n^2)$ is a loose upper bound for this, right? And the tighter one would be $O(n\lg n)$? $\endgroup$ May 8 at 0:26
  • $\begingroup$ @nir_shahar. I changed the information on the question because I was assuming the information was cut in half and it is not. It depends on the farthest point. How would that change the proof? $\endgroup$ May 8 at 1:04
  • $\begingroup$ @DarK_FirefoX I updated my answer according to it. $\endgroup$
    – nir shahar
    May 8 at 9:16
  • $\begingroup$ Thank you very much! I am only interested in the worst-case scenario, but your explanation of the other cases help me understand better the algortihm. $\endgroup$ May 8 at 16:30

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.