Time complexity

Contents

The time complexity represents in an asymptotic way the time that a algorithm to find a solution.

Let P be a problem and M be a method to solve this problem. The algorithm is a description with control and data structures allowing 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.).

Elementary operation

The complexity consists in evaluating the effectiveness of the method M and in comparing the latter 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 be the size of the data and T(n) the number of elementary operations. The evaluation of effectiveness will be done 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 treatment 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 branches. 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 passages. For example, if the algorithm is a while 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) = n log (n) if C (n) = n.

Landau notation

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

We say that f (n) is a large O of g (n) if

<img decoding="async" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f0f682cb36f62f6e9ffac5d9f2174a7f34c81b6b" alt="\ exists k&gt; 0, \ exists n_0 \; \ forall n&gt; n_0 \; | f (n) | \ leq | g (n) | \ cdot k " title="Time Complexity Time Complexity" width="16552.1" height="1223.9">

Examples

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 sum weighted by the probability of the presence of the possible complexities. Most often, we use worst-case complexity because we want to know an upper bound on the execution time.

Consider an algorithm for finding an element in an array in iterative form. The algorithm stops when the value has been found. The algorithm breaks down as follows: assignment of 0 to i, as long as i has not traversed the table one increments i, if tab[i]=value then one returns true, if not at the end of the table one returns false. Let C denote the complexity of the loop body.

In the worst case, the algorithm traverses the whole 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 array, and 50% that it is halfway through the array (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 (not). We notice that the asymptotic behavior on average is the same as in the worst case.

Examples

Suppose 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) with the greatest increase in n and specify the lowest Big-Oh complexity of each algorithm.

Expression	Dominant	O (.)
5 + 0.001n³+ 0.025n	0.001n³	We³)
500n + 100n^1.5 + 50n log₁₀ not	100n^1.5	We^1.5)
0.3n + 5n^1.5 + 2.5 n^1.75	2.5 n^1.75	We^1.75)
not² log₂ n + n (log₂ not)²	not² log₂ not	We² log n)
n log₃ n + n log₂ not	n log₃ n, n log₂ not	O (n log n)
3 log₈ n + log₂ log₂ log₂ not	3 log₈ not	O (log n)
0. 100n + 0.01n²	0.01n²	We²)
0.01n + 100n²	100n²	We²)
2n + n^0.5 + 0.5n^1.25	0.5n^1.25	We^1.25)
0.01n log₂ n + n (log₂ not)²	n (log₂ not)²	O (n (log n)²)
100n log₃ n + n³ + 100n	not³	We³)

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

Function	TRUE or FALSE?	After correction
O (f + g) = O (f) + O (g)	FALSE	O (f + g) = max {O (f), O (g)}
O (f g) = O (f) O (g)	TRUE
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	We³ )