Behavior of a Function

As seen in Section 2.1, the construction of an algorithm and/or a data structure requires evaluating the number of operations involved and, in addition, looking closely at memory problems.

Addressing these points involves analyzing the complexity in time as well as the complexity in size of the algorithm and/or the data structure. A simple and generic way to analyze these notions is to introduce a mathematical function f related to the size n of the inputs of the problem, where for instance, n is the number of points to be inserted in the triangulation. Finding the exact value of f( n) can be difficult or even impossible. However, we are usually not interested in this value, but rather in a rough estimate of it. Several ways of quantifying this point exist. The usual notations are f( n) ? ?( g( n)) or ?( g( n)) or or o( g( n)) which indicate respectively that, for a sufficiently large n and for a "known" g( n), we have:

• ?: c ₁ g( n) < f( n) < c ₂ g( n) where c ₁