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:
“Every time a child organizes and completes a chore, spends some time alone without feeling lonely, loses herself in play for an hour, or refuses to go along with her peers in some activity she feels is wrong, she will be building meaning and a sense of worth for herself and harmony in her family.”
—Barbara Coloroso (20th century)
“In times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...”
—Marcel Proust (18711922)