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: Example output: 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.
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.
Output-sensitive algorithms arise frequently in computational geometry applications and have been described for problems such as hidden surface removal[1] and resolving range filter conflicts in router tables.
[3] 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.