Content deleted Content added
No edit summary |
|||
Line 10:
[[Output-sensitive algorithm]]s define their complexity not only in terms of their input but also their output. For example, [[Chan's algorithm]] can compute the [[convex hull]] of a set of points in O(''n'' log ''h'') time, where ''n'' is the number of points in the input and ''h'' is the number of points in the resulting convex hull, a subset of the input points. Because every input point ''might'' be in the convex hull, an analysis in terms of the input alone would yield the less precise O(''n'' log ''n'') time.
The complexity of some algorithms depends not only on parameters of the input but also parameters of the machine the algorithm is being run on; as mentioned in [[#Metric being measured]] below, this is typical in analyzing algorithms that run on systems with fixed cache hierarchies, where the complexity may depend on parameters such as cache size and block size.
== Abstract machine ==
| |||