Studying an algorithm's resource use under a stated cost model. Time complexity, space complexity and amortized analysis answer different questions, so an operation count should specify the input-size parameter and what each primitive operation costs.
Average-case analysis measures an algorithm's expected cost when its inputs follow a specified probability distribution. If is the number of counted operations on input and is the probability of a size- input, then
The expected value is meaningful only after specifying both the input model and the counted operation. It is not an average over arbitrary anecdotes or necessarily the cost of a typical individual run.
For a successful linear search through distinct entries, suppose the sought entry is equally likely to occupy any position. Searching from the beginning uses comparisons if the entry is at position , so
For , this is five comparisons, whereas worst-case analysis gives nine. If the entry is absent with probability and otherwise has the same equal-position model, the expected count becomes . Changing the workload therefore changes the answer without changing the algorithm. Amortized analysis instead bounds the cost of a sequence of operations and need not assume an input probability distribution.
Worst-case analysis measures the largest resource use of a specified algorithm among inputs of the same size. If counts operations on input , the worst-case function is
The cost model and meaning of input size are part of the definition. A big O notation bound describes growth of this function, rather than a claim about how often the difficult input occurs.[ref]
For linear search of entries, looking for an absent item requires equality tests; finding the first item needs just one. Thus the worst-case comparison count is , even if many actual queries finish earlier. This supplies a guarantee for every allowed input, while an average-case analysis requires a stated distribution over inputs.
Arithmetic complexity counts arithmetic operations under an explicitly stated computational model. One may count additions, subtractions, multiplications and divisions over a specified field as unit operations, or distinguish their costs. This exposes algebraic structure without yet accounting for how each number is represented.
For a degree- polynomial , Horner's method sets and for . It returns using multiplications and additions. Repeatedly expanding each power independently would obscure this reuse of earlier work. An arithmetic circuit represents such dependencies as a finite network of arithmetic operations.
Bit complexity asks an additional question: how much work is required to perform those operations on the encoded numbers? Multiplying two large integers is one arithmetic operation but requires processing their bits. Intermediate numerators and denominators can also grow. Conversely, a small arithmetic-operation count does not bound round-off error; the numerical stability of an evaluation scheme is a separate property.
A method for proving that an algorithm must perform a certain amount of work: supply observations compatible with more than one possible input until enough information has been acquired to distinguish the required outputs. For exact membership in an arbitrary array, answering every inspected location with a value other than the target forces inspection of every location in the absent case, since any uninspected location could contain the target.

Articles by others on the same topic (0)

There are currently no matching articles.