Division by subtraction A simple example of an output-sensitive algorithm is given by the
division algorithm division by subtraction which computes the quotient and remainder of dividing two positive integers using only addition, subtraction, and comparisons: def divide(number: int, divisor: int) -> tuple[int, int]: """Division by subtraction.""" if divisor == 0: raise ZeroDivisionError if number = divisor: q += 1 r -= divisor return q, r Example output: >>> divide(10, 2) (5, 0) >>> divide(10, 3) (3, 1) This algorithm takes
Θ(Q) time, and so can be fast in scenarios where the quotient Q is known to be small. In cases where Q is large however, it is outperformed by more complex algorithms such as
long division.
Computational geometry Convex hull algorithms for finding the
convex hull of a finite set of points in the plane require Ω(
n log
n) time for
n points; even relatively simple algorithms like the
Graham scan achieve this lower bound. If the convex hull uses all
n points, this is the best we can do; however, for many practical sets of points, and in particular for random sets of points, the number of points
h in the convex hull is typically much smaller than
n. Consequently, output-sensitive algorithms such as the
ultimate convex hull algorithm and
Chan's algorithm which require only O(
n log
h) time are considerably faster for such point sets. Output-sensitive algorithms arise frequently in
computational geometry applications and have been described for problems such as
hidden surface removal and resolving
range filter conflicts in router tables. Frank Nielsen describes a general paradigm of output-sensitive algorithms known as
grouping and querying and gives such an algorithm for computing cells of a
Voronoi diagram. Nielsen breaks these algorithms into two stages: estimating the output size, and then building data structures based on that estimate which are queried to construct the final solution. == Generalizations ==