Question

What is the running time of Hershberger algorithm?

(a) O(log n)

(b) O(n log n)

(c) O(n log h)

(d) O(log h)

This question was addressed to me in homework.

My enquiry is from Computational Geometry topic in section Computational Geometry of Data Structures & Algorithms II

Answer 1

The correct answer is (b) O(n log n)

Easy explanation - Hershberger’s algorithm is an output sensitive algorithm whose running time was originally O(n log n). He used Chan’s algorithm to speed up to O(n log h) where h is the number of edges.