Editing Graham scan (section)

== Time complexity ==
{{uncited-section|date=February 2024}}
Sorting the points has time complexity O(''n'' log ''n''). 
While it may seem that the time complexity of the loop is O(''n''<sup>2</sup>), because for each point it goes back to check if any of the previous points make a "right turn", it is actually O(''n''), because each point is considered at most twice in some sense.
Each point can appear only once as a point <math>(x_2,y_2)</math> in a "left turn" (because the algorithm advances to the next point <math>(x_3,y_3)</math> after that),
and as a point <math>(x_2,y_2)</math> in a "right turn" (because the point <math>(x_2,y_2)</math> is removed). The overall time complexity is therefore O(''n'' log ''n''), since the time to sort dominates the time to actually compute the convex hull.