Complexity of the QuickHull Algorithm?

algorithm, c++, computational-geometry, java, sorting

Solution

Its average case complexity is considered to be `O(n log(n))`, whereas in the worst case it takes `O(n^2)` (quadratic).

Consider the following pseudo-code:

QuickHull (S, l, r)

     if S={ }    then return ()
else if S={l, r} then return (l, r)  // a single convex hull edge
else
    z = index of a point that is furthest (max distance) from xy.
    Let A be the set containing points strictly right of (x, z)
    Let B be the set containing points strictly right of (z, y)
    return {QuickHull (A, x, z) U (z) U QuickHull (B, z, y)}

The partition is determined by the line passing through two distinct extreme points: the rightmost lowest `r` and the leftmost highest points `l`. Finding the extremes require `O(n)` time.

For the recursive function, it takes `n` steps to determine the extreme point `z`, but the cost of recursive calls depends on the sizes of set `A` and set `B`.

Best case. Consider the best possible case, when each partition is almost balanced. Then we have

`T(n) = 2 T(n/2) + O(n)`.

This is a familiar recurrence relation, whose solution is

`T(n) = O(n log(n))`.

This would occur with randomly distributed points.

Worst case. The worst case occurs when each partition is an extremely unbalanced. In that case the recurrence relation is

T(n) = T(n-1) + O(n) 
     = T(n-1) + cn

Repeated expansion shows this is `O(n^2)`. Therefore, in the worst case the QuickHull is quadratic.

http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/ConvexHull/quickHull.htm

Problem

I know the complexity is O(nlog(n)). But why? How do you come to this answer? Any help would be much appreciated, I'm very interested to know!

Original source