Douglas-Peucker line simplification algorithm time complexity 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:

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.
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.