## Basic operation

The complexity consists in evaluating the efficiency of the method M and comparing it with another method M’. This comparison is independent of the environment (machine, system, compiler, language, etc.). Efficiency depends on the number of elementary operations. These depend on the size of the data and the nature of the data.

In the case of a sequence type structure, the evaluation is equal to the sum of the costs. For example, if the algorithm has a processing T1(n) followed by T2(n), then T(n)=T1(n)+T2(n).

In the case of a branch, the evaluation is equal to the maximum of the branch lines. For example, the algorithm executes T1(n) else T2(n), then T(n)=max(T1(n), T2(n)).

In the case of a loop, the evaluation is equal to the sum of the costs of the successive passes. For example, if the algorithm is a « while doing Ti(n) with the complexity of Ti(n) depending on the number i of the iteration. » Then the complexity is T(n)=sum(i=1 to n)Ti(n).

## Landau’s notation

Landau’s notation characterizes the asymptotic behavior of a function, that is, the behavior of f(n) when n tends to infinity.

## Example

factorial(int n)

{ int fact = 1; //O(1): initialization

int i = 2; //O(1): initialization

while( i <= n) { //(n − 1) iteration

fact = fact ∗ i; //O(1): multiplication

i = i + +; //O(1): incrementation

}

return fact; //O(1): return

}

Complexity is equal to:

O(1) +O(1) +O((n −1) ∗ (1+1)) +O(1) = O(n)

while(low ≤ high) {

id = (low + high)/2;

if (target < list[mid]) high = mid − 1; else if (target > list[mid])

low = mid + 1;

else break; }

This algorithm will have a Logarithmic Time Complexity O(log(n)). The running time of the algorithm is proportional to the number of times N can be divided by 2 (N is high-low here) which is log(n) in binary.

## Worse, better and average

Consider an algorithm for finding an element in a table in iterative form. The algorithm stops when the value has been found. The algorithm is broken down as follows: assignment of 0 to i, as long as i has not traversed the table we increment i, if tab[i]=value then we return true, otherwise at the end of the array we return false. Note C the complexity of the loop.

In the worst case, the algorithm traverses the entire array, ie T(n)=1+n*C=O(n). At best, the element is at the beginning of the array, so T(n)=1+C=O(1). We consider that on average, there is a 50% chance that the element is not in the table, and 50% that it is at half of the table (this is of course absurd, but we will not do all the possibilities). In this case, the average complexity is T(n)=0.5*(1+n*C)+0.5*(1+n*C/2)=a*n+b with a and b constants =O(n). We notice that the average asymptotic behavior is the same as the worst case.

## Examples

Assume that each of the expressions below gives the processing time T(n) spent by an algorithm to solve a problem of size n. Select the dominant term(s) having the steepest increase in n and specify the lowest Big-Oh complexity of each algorithm.

Expression |
Dominant term(s) |
O(.) |

5 + 0.001n^{3}+ 0.025n |
0.001n^{3} |
O(n^{3}) |

500n + 100n^{1.5} + 50n log_{10} n |
100n^{1.5} |
O(n^{1.5}) |

0.3n + 5n^{1.5} + 2.5 n^{1.75} |
2.5 n^{1.75} |
O(n^{1.75}) |

n^{2} log_{2} n + n(log_{2} n)^{2} |
n^{2} log_{2} n |
O(n^{2} log n) |

n log_{3} n + n log_{2} n |
n log_{3} n, n log_{2} n |
O(n log n) |

3 log_{8} n + log_{2} log_{2} log_{2} n |
3 log_{8} n |
O(log n) |

0. 100n + 0.01n^{2} |
0.01n^{2} |
O(n^{2}) |

0.01n + 100n^{2} |
100n^{2} |
O(n^{2}) |

2n + n^{0.5} + 0.5n^{1.25} |
0.5n^{1.25} |
O(n^{1.25}) |

0.01n log_{2} n + n(log_{2} n)^{2} |
n(log_{2} n)^{2} |
O(n(log n)^{2}) |

100n log_{3} n + n^{3} + 100n |
n^{3} |
O(n^{3}) |

The statements below show some features of “Big-Oh” notation for the functions f ≡ f(n) and g ≡ g(n). Determine whether each statement is TRUE or FALSE and correct the formula in the latter case.

Statement |
TRUE or FALSE ? |
If FALSE then write the correct formula |

Rule of sums:
O(f + g) = O(f) + O(g) |
FALSE | O(f + g) = max {O(f), O(g)} |

Rule of products:
O(f · g) = O(f) · O(g) |
TRUE | |

Transitivity:
if g = O(f) and h = O(f) then g = O(h) |
FALSE | if g = O(f) and f = O(h) then g = O(h) |

5n + 8n 2 + 100n 3 = O(n 4 ) | TRUE | |

5n+8n 2 +100n 3 = O(n 2 log n) | FALSE | O(n^{3} ) |