2018 | OriginalPaper | Chapter

# 11. Asymptotic Analysis

Published in:
The Discrete Math Workbook

## Abstract

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.