Editing Algorithm (section)

== Algorithmic analysis ==
{{Main|Analysis of algorithms}}

It is often important to know how much time, storage, or other cost an algorithm may require. Methods have been developed for the analysis of algorithms to obtain such quantitative answers (estimates); for example, an algorithm that adds up the elements of a list of ''n'' numbers would have a time requirement of {{tmath|O(n)}}, using [[big O notation]]. The algorithm only needs to remember two values: the sum of all the elements so far, and its current position in the input list. If the space required to store the input numbers is not counted, it has a space requirement of {{tmath|O(1)}}, otherwise {{tmath|O(n)}} is required.

Different algorithms may complete the same task with a different set of instructions in less or more time, space, or '[[algorithmic efficiency|effort]]' than others. For example, a [[binary search]] algorithm (with cost {{tmath|O(\log n)}}) outperforms a sequential search (cost {{tmath|O(n)}} ) when used for [[lookup table|table lookup]]s on sorted lists or arrays.

===Formal versus empirical===
{{Main|Empirical algorithmics|Profiling (computer programming)|Program optimization}}

The [[analysis of algorithms|analysis, and study of algorithm]]s is a discipline of [[computer science]]. Algorithms are often studied abstractly, without referencing any specific [[programming language]] or implementation. Algorithm analysis resembles other mathematical disciplines as it focuses on the algorithm's properties, not implementation. [[Pseudocode]] is typical for analysis as it is a simple and general representation. Most algorithms are implemented on particular hardware/software platforms and their [[algorithmic efficiency]] is tested using real code. The efficiency of a particular algorithm may be insignificant for many "one-off" problems but it may be critical for algorithms designed for fast interactive, commercial, or long-life scientific usage. Scaling from small n to large n frequently exposes inefficient algorithms that are otherwise benign.

Empirical testing is useful for uncovering unexpected interactions that affect performance. [[Benchmark (computing)|Benchmark]]s may be used to compare before/after potential improvements to an algorithm after program optimization.
Empirical tests cannot replace formal analysis, though, and are non-trivial to perform fairly.<ref name="KriegelSchubert2016">{{cite journal|last1=Kriegel|first1=Hans-Peter|author-link=Hans-Peter Kriegel|last2=Schubert|first2=Erich|last3=Zimek|first3=Arthur|author-link3=Arthur Zimek|title=The (black) art of run-time evaluation: Are we comparing algorithms or implementations?|journal=Knowledge and Information Systems|volume=52|issue=2|year=2016|pages=341–378|issn=0219-1377|doi=10.1007/s10115-016-1004-2|s2cid=40772241}}</ref>

=== Execution efficiency ===
{{Main|Algorithmic efficiency}}

To illustrate the potential improvements possible even in well-established algorithms, a recent significant innovation, relating to [[Fast Fourier transform|FFT]] algorithms (used heavily in the field of image processing), can decrease processing time up to 1,000 times for applications like medical imaging.<ref>{{cite web| title=Better Math Makes Faster Data Networks| author=Gillian Conahan| date=January 2013| url=http://discovermagazine.com/2013/jan-feb/34-better-math-makes-faster-data-networks| publisher=discovermagazine.com| access-date=May 13, 2014| archive-url=https://web.archive.org/web/20140513212427/http://discovermagazine.com/2013/jan-feb/34-better-math-makes-faster-data-networks| archive-date=May 13, 2014| url-status=live}}</ref> In general, speed improvements depend on special properties of the problem, which are very common in practical applications.<ref name="Hassanieh12">Haitham Hassanieh, [[Piotr Indyk]], Dina Katabi, and Eric Price, "[http://siam.omnibooksonline.com/2012SODA/data/papers/500.pdf ACM-SIAM Symposium On Discrete Algorithms (SODA)] {{webarchive|url=https://web.archive.org/web/20130704180806/http://siam.omnibooksonline.com/2012SODA/data/papers/500.pdf |date=July 4, 2013 }}, Kyoto, January 2012. See also the [http://groups.csail.mit.edu/netmit/sFFT/ sFFT Web Page] {{Webarchive|url=https://web.archive.org/web/20120221145740/http://groups.csail.mit.edu/netmit/sFFT/ |date=February 21, 2012 }}.</ref> Speedups of this magnitude enable computing devices that make extensive use of image processing (like digital cameras and medical equipment) to consume less power.

==== Best Case and Worst Case ====
The best case of an algorithm refers to the scenario or input for which the algorithm or data structure takes the least time and resources to complete its tasks.<ref>{{Cite web |title=Best Case |url=https://xlinux.nist.gov/dads/HTML/bestcase.html |access-date=29 May 2025 |website=Dictionary of Algorithms and Data Structures |publisher=National Institute of Standards and Technology (NIST) |agency=National Institute of Standards and Technology}}</ref>  The worst case of an algorithm is the case that causes the algorithm or data structure to consume the maximum period of time and computational resources.<ref>{{Cite web |title=worst case |url=https://xlinux.nist.gov/dads/HTML/worstcase.html |access-date=29 May 2025 |website=Dictionary of Algorithms and Data Structures |publisher=National Institute of Standards and Technology (NIST) |agency=National Institute of Standards and Technology (NIST)}}</ref>