algorithm efficiency

Quick Reference

A measure of the average execution time necessary for an algorithm to complete work on a set of data. Algorithm efficiency is characterized by its order. Typically a bubble sort algorithm will have efficiency in sorting N items proportional to and of the order of N2, usually written O(N2). This is because an average of N/2 comparisons are required N/2 times, giving N2/4 total comparisons, hence of the order of N2. In contrast, quicksort has an efficiency O(N log2N).

If two algorithms for the same problem are of the same order then they are approximately as efficient in terms of computation. Algorithm efficiency is useful for quantifying the implementation difficulties of certain problems.

Subjects: Computing.

Reference entries