# Why triangulation algorithms takes quadratic time in worst case?

The book says triangulation algorithm takes quadratic time in worst case. but why? The book says - take leftmost vertex and try to connect its neighbors. If you succeed - you get triangle and polygon

and therefore as the consequence you get quadratic time algo. But why? I made this procedure and for a polygon of 7 vertices I performed 4 divisions...

In general I do not see how quadratic time is possible... cannot come up with an instance.

• Trying to get an idea about the complexity of something by doing by hand the case n=7 has very little chance of being useful. Feb 13 '18 at 2:30

Your diagrams are of convex polygons. The algorithm is for a polygon which may be decidedly concave, with hundreds of edges crossing the $uw$ line.
• Millions even. ${}$ Feb 13 '18 at 2:29