Swipe to navigate through the chapters of this book
An important task of algorithm analysis is the estimation of the number of operations executed by the algorithm over a certain class of input data. The exact value of the number of elementary operations does not play any considerable role here, since it depends on the software implementation of the algorithm, the computer’s architecture, and other factors. This is why the algorithm’s performance indicator is the growth rate of this value with the growth of the input data volume.
For analysis of the algorithm’s efficiency, it is necessary to estimate the operation time of the computer that solves the set problem, as well as the volume of memory used. The estimate of the computation system operation time is usually obtained by calculating the elementary operations performed during calculations (such operations are referred to as basic). In a supposition that one elementary operation is executed within a strictly defined period of time, the function f(n), defined as the number of operations when calculating over the input data of size n, is called a time-complexity function.
Universal method of estimating the growth rate of functions, based on the Master Theorem, is given.
Please log in to get access to this content
To get access to this content you need the following product:
James Stirling (1692–1770)—Scottish mathematician.
Guillaume François Antoine, marquis de L’Hôpital (1661–1704)—French mathematician.
Jon Louis Bentley (born 1953), Dorothea Haken, James Benjamin Saxe—American mathematicians.
Paul Gustav Heinrich Bachmann (1837–1920)—German mathematician.
Edmund Georg Hermann Landau (1877–1938)—German mathematician.
Donald Ervin Knuth (born 1938)—American scientist, specializing in the sphere of informatics and computing.
Volker Strassen (born 1936)—German mathematician.
- Asymptotic Analysis
- Springer International Publishing
- Sequence number
- Chapter number
- Chapter 11