Graham Scan - Time Complexity

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:

    “last time I saw you was the hospital
    pale skull protruding under ashen skin
    blue veined unconscious girl
    in an oxygen tent
    the war in Spain has ended long ago
    Aunt Rose”
    —Allen Ginsberg (b. 1926)

    “It is not only their own need to mother that takes some women by surprise; there is also the shock of discovering the complexity of alternative child-care arrangements that have been made to sound so simple. Those for whom the intended solution is equal parenting have found that some parents are more equal than others.”
    —Elaine Heffner (20th century)