Overview
Algorithm efficiency describes how effectively an algorithm uses computational resources to solve a problem. The two most common resources examined are execution time and memory. An efficient algorithm aims to achieve the required result while using resources appropriately for the expected workload and system constraints.
Time Efficiency
Time efficiency concerns how the computational work performed by an algorithm grows as the input becomes larger. It is commonly analyzed by counting fundamental operations such as comparisons, assignments, arithmetic operations, or array accesses rather than relying only on the elapsed time of one particular execution.
Space Efficiency
Space efficiency concerns the memory required during execution. This includes variables, temporary data structures, recursion stack frames, and other auxiliary storage. Depending on the analysis, input storage and output storage may be reported separately from auxiliary space.
Scalability
Scalability describes how an algorithm behaves when the input size increases. A method that works well on a small dataset may become impractical when processing millions of records. Growth rates are therefore important when choosing an algorithm.
Operation Counting
Operation counting estimates the number of elementary operations performed as a function of input size. For example, a single traversal of an array of n elements performs a number of element inspections proportional to n.
Asymptotic Efficiency
Asymptotic analysis studies the growth of resource requirements as input size approaches large values. It allows algorithms to be compared independently of many hardware-specific details.
Practical Performance
Actual execution time also depends on hardware, compiler or interpreter behavior, memory access patterns, cache performance, implementation quality, and workload characteristics. Complexity analysis provides a theoretical model, not an exact prediction of elapsed time.
Constant Factors
Two algorithms may have the same asymptotic complexity but different practical performance because of constant factors and lower-order terms. For small inputs, these differences can be more important than the asymptotic growth rate.
Resource Constraints
An algorithm must be evaluated in the context of available resources. A memory-intensive method may be unsuitable for a device with limited memory, while a slower method may be acceptable when memory usage must remain very low.
Efficiency And Correctness
Efficiency is meaningful only after the algorithm satisfies its correctness requirements. An optimization that changes the required output or introduces incorrect behavior is not a valid improvement.