Time complexity

Let P be a problem and M be a method to solve this problem. The algorithm is a description with control structures and data to write the method M in a language recognizable by any individual or machine.
As a reminder, the control structures are: a sequence, a branch (or selection), a loop (or iteration). Data structures are: constants, variables, arrays (or ordered storage space), recursive structures (lists, graphs, etc.).

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.

Let n denote the size of the data and T(n) the number of elementary operations. The evaluation of effectiveness will be in the best case, the worst case and the average case.

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).

For a recursive version, I invite you to go to the corresponding page. Let C(n) be the processing performed in a divide & conquer function. Then the complexity is T(n)=2*T(n/2)+C(n)=nlog(n) if C(n)=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.

We say that f(n) is a Big O of g(n) si.\exists k>0, \exists n_0 \; \forall n>n_0 \; |f(n)| \leq |g(n)|\cdot k .

complexity1

 complexity

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

We can calculate for most algorithms a complexity in the worst case (the greatest number of elementary operations), the best and on average. The average is a weighted sum of the probability of presence of possible complexities. Most often, the complexity is used for the worst because we wish to know an upper bound of the execution time.

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.001n3+ 0.025n 0.001n3 O(n3)
500n + 100n1.5 + 50n log10 n 100n1.5 O(n1.5)
0.3n + 5n1.5 + 2.5 n1.75 2.5 n1.75 O(n1.75)
n2 log2 n + n(log2 n)2 n2 log2 n O(n2 log n)
n log3 n + n log2 n n log3 n, n log2 n O(n log n)
  3 log8 n + log2 log2 log2 n 3 log8 n O(log n)
0. 100n + 0.01n2 0.01n2 O(n2)
0.01n + 100n2 100n2 O(n2)
2n + n0.5 + 0.5n1.25 0.5n1.25 O(n1.25)
0.01n log2 n + n(log2 n)2 n(log2 n)2 O(n(log n)2)
100n log3 n + n3 + 100n n3 O(n3)

 

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(n3 )

 

Publicités