Time Complexity
Sorting the points has time complexity O(n log n). While it may seem that the time complexity of the loop is O(n2), 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 in a "left turn" (because the algorithm advances to the next point after that), and as a point in a "right turn" (because the point 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.
Read more about this topic: Graham Scan
Famous quotes containing the words time and/or complexity:
“When autonomy is respected, the two-year-old does not carry this unfinished task into later stages of growth. In adolescence, the youngster will again concentrate on independence, but he won’t have to blast the roof off the second time around if it is already well established.”
—Dorothy Corkville Briggs (20th century)
“The price we pay for the complexity of life is too high. When you think of all the effort you have to put in—telephonic, technological and relational—to alter even the slightest bit of behaviour in this strange world we call social life, you are left pining for the straightforwardness of primitive peoples and their physical work.”
—Jean Baudrillard (b. 1929)