The complexity of an algorithm is measured by the operations needed to solve the corresponding problem.
We are concerned with estimating the complexity of algorithms, where the number of operations
depends on the size of the input. Examples of such algorithms are:

• reading a file: the number of read operations depends on the number of records in the file
• finding a name in a list of names:
  the number of operations depend on the number of the names in the list
• finding the greatest element in an array of elements:
  the number of operations depends on the length of the array.

If N is the number of the elements to be processed by an algorithm (N is the size of the input)
then the number of operations can be represented as a function of N: f(N)
(sometimes we use small n)

We can compare the complexity of two algorithms by comparing the corresponding functions.
Moreover, we are interested what happens with the functions for large N,
i.e. we are interested in the asymptotic growth of these functions.

Each particular growing function has its own speed of growing.
Ssome functions grow faster, others grow slower.

The question is: ? Is there a way to compare the rate of growth of two functions?

The rate of growth of a function is called asymptotic growth.
We can compare functions by studying their asymptotic growth.

Given a function f(n), all other functions fall into three classes:

1. growing with the same rate as f(n)
2. growing faster than f(n)
3. growing slower than f(n)

• CASE 1: f(n) and g(n) have the same rate of growing, if

lim(f(n)/g(n)) = c, 0 < c < ∞, n → ∞

Notation: f(n) = Θ(g(n)) , pronounced "theta"

 

• CASE 2: f(n) grows slower than g(n) (i.e g(n) grows faster than f(n)) if

lim(f(n)/g(n)) = 0, n → ∞

Notation: f(n) = o(g(n)), pronounced "little oh"

 

• CASE 3: f(n) grows faster than g(n) ( i.e. g(n) grows slower than f(n)) if

lim(f(n)/g(n)) = ∞, n → ∞

Notation: f(n) = ω (g(n)), pronounced "little omega"

1. Case 2 and Case 3.

Obviously, case 2 is the reverse of case 3:

if


g(n) = o( f(n) ),
then
f(n) = ω( g(n) )

Examples :

Compare n and n²

lim( n/n² ) = 0, n → ∞, hence n = o(n²),

lim( n²/n ) = ∞, n → ∞, hence n² = ω(n)

Compare n and log n

lim( (log n) / n ) = 0, n → ∞, hence log n = o(n),

lim( n / log n ) = ∞, n → ∞, hence n = ω (log n),

2. Case 1 in details

f(n) and g(n) have the same rate of growth if

lim( f(n)/g(n) ) = c, 0 < c < ∞, n → ∞

Let Θ( f(n) ) be the set of all functions, that grow with the rate of f(n).
If g(n) has the same rate of growth, then g(n) є Θ( f(n) ).

Consider the properties of the relation: "having the same rate of growth":

1. The relation is symmetric:
   If g(n) grows with the same rate as f(n), then f(n) grows with the same rate as g(n),
   hence if f(n) = Θ(g(n)) then g(n) = Θ(f(n))

2. The relation is transitive:
   Obviously, if g(n) = Θ(f(n)) and f(n) = Θ(h(n)) then g(n) = Θ(h(n))
3. The relation is reflexive:
   g(n) = Θ(g(n))

Hence this is a relation of equivalence and it gives a partition over the set of all functions - classes of equivalence.
Thus functions in one and the same class are equivalent with respect to their growth.

The important result is:

Two algorithms have same complexity,
if the functions representing the number of operations have same rate of growth,
i.e. if they belong to one and the same class of equivalence.
Among all functions in a given class of equivalence we choose the simplest one
to represent the complexity for that class.

Note: In Theory of Algorithms we use '=' instead of 'є' : g(n) = Θ(f(n))

The Big-Oh notation is used to simplify our reasoning about growth rates.

f(n) = O( g(n) ) if f(n) grows with the same rate or slower than g(n).

i.e. if f(n) = Θ(g(n)) or f(n) = o(g(n)), then we write f(n) = O(g(n))

Thus n+5 = Θ(n) = O(n) = O(n²) = O(n³) = O(n⁵)

While all the equalities are technically correct, we would like to have the closest estimation:

However, the general practice is to use the Big-Oh notation and to write:

Big-Omega notation is the inverse of the Big-Oh:

Here we say that f(n) grows faster or with the same rate as g(n), and write

In the analysis of algorithms we shall use mainly the Big-Oh estimate.

Let T(N) (and also T1(N), T2(N)) denote the run time of an algorithm for input of size N

1. If T1(N) = O( f(N) ) and T2(N) = O( g(N) ) then

   T1(N) + T2(N) = max( O( f(N) ), O( g(N) ))
   where max( O( f(N) ), O( g(N) )) is the faster growing function.

2. If T1(N) = O( f(N) ) and T2(N) = O( g(N) ) then

   T1(N) * T2(N) = O( f(N) * g(N) )

Rule 2: If T(N) is a polynomial of degree k, then T(N) = Θ(N^k)

Rule 3: log^kN = O(N) for any constant k.

x² = O(x²), actually x² = Θ (x²)

2x² = O(2x²) = O(x²), we do not consider coefficients

x² + x = O(x²), we disregard any lower-order term

xlog(x) = O(xlog(x))