Introduction to algorithm complexity analysis (part 2)

From the translator: this text is given with insignificant abbreviations due to places of excessive “razvezhnannosti” material. The author absolutely rightly warns that certain topics may seem too simple or well-known to the reader. Nevertheless, personally this text helped me to streamline the existing knowledge on the analysis of the complexity of algorithms. I hope that it will be useful to someone else.
Due to the large volume of the original article, I broke it into pieces, which in total will be four.
I (as always) would be extremely grateful for any comments in PM about improving the quality of the translation.

Published previously:
Part 1

Complexity

From the previous part, we can conclude that if we can discard all these decorative constants, then it will be very easy to talk about the asymptotic behavior of the program instruction counting function. In fact, any program that does not contain cycles has f( n ) = 1 , because in this case a constant number of instructions is required (of course, in the absence of recursion - see below). A single cycle from 1 to n gives the asymptotics f( n ) = n , since before and after the cycle it performs a constant number of commands, and the constant number of instructions within the cycle is executed n times.

Guided by such considerations is less tedious than reading instructions each time, so let's look at a few examples of how to consolidate this material. The following PHP program checks whether the array A size n contains the specified value:
')

 <?php $exists = false; for ( $i = 0; $i < n; ++$i ) { if ( $A[ $i ] == $value ) { $exists = true; break; } } ?> 

This method of searching for values ​​inside an array is called a linear search . This is a valid name, since the program has f( n ) = n (which means “linear” more precisely, we will look at the next section). The break allows the program to complete earlier, even after a single iteration. However, I remind you that we are interested in the most unfavorable scenario, in which the array A does not contain the specified value at all. Therefore, f( n ) = n is still.



Let's look at a Python program that adds two values ​​from an array and writes the result to a new variable:

 v = a[ 0 ] + a[ 1 ] 

Here we have a constant number of instructions, therefore, f( n ) = 1 .

The following C ++ program checks whether a vector (a kind of array) contains A size n two identical values:

 bool duplicate = false; for ( int i = 0; i < n; ++i ) { for ( int j = 0; j < n; ++j ) { if ( i != j && A[ i ] == A[ j ] ) { duplicate = true; break; } } if ( duplicate ) { break; } } 

Two nested cycles will give us the asymptotics of the form f( n ) = n ² .

---

Practical recommendation : simple programs can be analyzed by counting the number of nested loops. A single loop in n iterations gives f( n ) = n . The loop inside the loop is f( n ) = n ² . The loop inside the loop inside the loop is f( n ) = n ³ . And so on.

---

If in our program a function is called in the loop body, and we know the number of instructions executed in it, then it is easy to determine the total number of instructions for the program as a whole. Consider the following C code as an example:

 int i; for ( i = 0; i < n; ++i ) { f( n ); } 

If we know that f( n ) executes exactly n instructions, then we can say that the number of instructions in the entire program asymptotically approaches n ² , since f( n ) is called n times.

---

Practical recommendation : if we have a series of consecutive for-cycles, then the asymptotic behavior of the program determines the slowest of them. Two nested loops that follow a single loop are asymptotically the same as nested loops themselves. Nested loops are said to dominate single ones.

---

Now let's switch to an interesting notation used by theorists. When we figure out the exact asymptotic behavior of f , we say that our program is Θ( f( n ) ) . For example, in the examples above, the programs Θ( 1 ) , Θ( n ² ) and Θ( n ² ) , respectively. Θ( n ) pronounced “theta by n”. Sometimes we say that f( n ) (the original function of counting instructions, including constants) is Θ( - ) . For example, we can say that f( n ) = 2n is a function that is Θ( n ) . In general, nothing new. You can also write that 2n ∈ Θ( n ) , which is pronounced: “two n belongs to theta from n”. Do not be confused by this notation: it simply says that if we count the number of commands required by the program, and it will be equal to 2n , then the asymptotics of this algorithm is described as n (which we find by discarding the constant). Having this notation, we present several true mathematical statements:

1. n ⁶ + 3n ∈ Θ (n ⁶ )
2. 2 ⁿ + 12 ∈ Θ (2 ⁿ )
3. 3 ⁿ + 2 ⁿ ∈ Θ (3 ⁿ )
4. n ⁿ + n ∈ Θ (n ⁿ )

By the way, if you decide exercise 1 from the first part, then this is his correct answer.

We call this function (that is, what we write Θ( ) ) the time complexity , or simply the complexity of our algorithm. Thus, the algorithm with Θ( n ) has complexity n . There are also special names for Θ( 1 ) , Θ( n ) , Θ( n ² ) and Θ( log( n ) ) , because they are very common. They say that Θ( 1 ) is an algorithm with constant time , Θ( n ) is linear , Θ( n ² ) is quadratic , and Θ( log( n ) ) is logarithmic (do not worry if you still do not know what logarithm - we'll talk about it soon).

---

Practical recommendation : programs with a large Θ run slower than with a smaller one.

---

Notation "big o"

In real life, it is sometimes problematic to find out the exact behavior of an algorithm in the way we considered above. Especially for more complex examples. However, we can say that the behavior of our algorithm will never cross a certain boundary. This makes life easier, as a clear indication of how fast our algorithm is, we may not appear, even if the constants are ignored (as before). All we need is to find this boundary, and how to do it is easier to explain with an example.

The most famous task that is used in teaching algorithms is sorting. An array A size n (sounds familiar, isn't it?), And we are asked to write a program that sorts it. Interest here is that such a need often arises in real systems. For example, a file browser needs to sort files by name in order to make it easier for users to navigate through them. Or another example: in a video game, there may be a problem of sorting 3D objects displayed on the screen according to their distance from the player’s point of view in the virtual world. Purpose: to determine which of them will be visible to him, and which - no (this is called the Visibility Problem ). Sorting is also interesting because for it there are many algorithms, some of which are worse than others. Also this task is simple for definition and explanation. So let's write a piece of code that will sort the array.

 b = [] n.times do m = a[ 0 ] mi = 0 a.each_with_index do |element, i| if element < m m = element mi = i end end a.delete_at( mi ) b << m end 

This is a completely inefficient way to implement array sorting in Ruby. (Of course, Ruby supports sorting arrays using built-in functions, which should be used. They are undoubtedly faster than the code above, presented for illustrative purposes only.)

This method is called sorting by choice . First is the minimum element of the array ( a in the code above. The minimum is designated as m , and its index is mi ), which is placed at the end of the new array ( b in our case) and removed from the original. Then, among the remaining values, the minimum is again, added to the new array (which now contains two values) and removed from the old one. The process is repeated until all elements are transferred from the original to the new array, which means the end of sorting. In our example, we have two nested loops. The outer loop “runs through” n times, and the inner loop once for each element of the array a . Since initially a has n elements and at each iteration we delete one of them, first the internal cycle “scrolls” n times, then n - 1 , n - 2 and so on, until at the last iteration the internal cycle passes only once.

If we consider the sum of 1 + 2 + ... + (n - 1) + n , then finding the complexity of this code will be somewhat problematic. But we can find an “upper limit” for it. To do this, we change the program (you can mentally, without touching the code) to make it worse than it is, and then we derive the complexity for what happened. Then you can confidently say that the original program works either as badly or (most likely) better.

Let's now think about how we change the program to simplify the conclusion of complexity for it. Do not forget: we can only worsen it (for example, adding new instructions to the code) so that our assessment makes sense for the original program. Obviously, we can change the internal program loop, forcing it to be calculated n times at each iteration. Some of these repetitions will be useless, but it will help us analyze the complexity of the resulting algorithm. If we make this small change, then our new algorithm will have Θ( n ² ) , because we get two nested loops, each of which is executed exactly n times. And if so, then the original algorithm has O( n ² ) . O( n ² ) pronounced "big O from n squared." This suggests that our program is asymptotically no worse than n ² . It will work either better or also. By the way, if the code really has Θ( n ² ) , then we still say that it is O( n ² ) . To better understand this, imagine that changing the original program does not change it much, making it only slightly worse. Something like adding useless instructions to the beginning of a program. This will only change the constant in the instruction calculation function, which we ignore in the asymptotics. Thus, Θ( n ² ) for the program is O( n ² ) too.

But the opposite is not always true. For example, any code with Θ( n ) also O( n ² ) in addition to O( n ) . If we imagine that the Θ( n ) program is just a for loop that runs n times, we can make it worse by adding another for inside, also repeating n times. This will give a program with f( n ) = n ² . To summarize: any program with Θ( a ) is O( b ) with b worse than a . Notice also that the change does not have to make sense or create code similar to the original one. All that is required of him is to increase the number of instructions in relation to the given n . We use the result to count instructions, not to solve a problem.

So, saying that the program has O( n ² ) , we are safe: the analysis of the algorithm has shown that it will never work worse than n ² . This gives us a good assessment of how fast our program is. Let's solve a few examples so that you get a better idea of ​​the new notation.





Since complexity of the algorithm represents the upper limit of its present complexity, which, in turn, reflects Θ , sometimes we say that Θ gives us an accurate estimate . If we know that the boundary we found is not exact, we can use a lower-case to denote it. For example, if the algorithm is Θ( n ) , then its exact complexity is n . Therefore, this algorithm is O( n ) and O( n ² ) at the same time. Since the algorithm is Θ( n ) , then O( n ) defines the boundary more precisely. And we can write O( n ² ) as ( n ² ) (pronounced "small o from n squared") to show what we know about the lack of strictness of the border. Of course, it is better when we can find the exact boundaries for our algorithm in order to have more information about its behavior, but, unfortunately, this is not always easy to do.

---

Practical recommendation : to find out the O complexity of the algorithm is simpler than its Θ complexity.

---

By now, you might already have gotten confused in all these new notations, but let's get acquainted with two more symbols before proceeding to the further examples. Above, we changed our program to make it worse (we increased the number of instructions and, thus, the execution time), than we created the O-notation. tells us that our code will never run slower than a certain limit. From this we get a basis for evaluation: is our program good enough? If we act in the opposite way, having made the existing code better , and we find the complexity of what happens, then we will use the Ω-notation. Thus, Ω gives us complexity, beyond which our program cannot be. It is useful if we want to prove that the program is slow or the algorithm is bad. It can also be used when we say that the algorithm is too slow to use in this particular case. For example, the statement that the algorithm is Ω( n ³ ) means that the algorithm is no better than n ³ . It may be Θ( n ³ ) , or Θ( n ⁴ ) , or even worse, but we will know the limit of its “goodness”. Thus, Ω gives us the lower limit of the complexity of our algorithm. Similarly to ο , we can write ω if we know that this limit is not strict. For example, Θ( n ³ ) algorithm is ο( n ⁴ ) and ω( n ² ) . Ω( n ) pronounced “omega large from n”, while ω( n ) pronounced “omega small from n”.



The reason why we use O and Ω instead of Θ that we may not be sure of the accuracy of the bounds we found or simply do not want to dig the algorithm deeper.

If you do not fully remember all this variety of symbols, do not worry. You can always come back and refresh information on them. The most important characters are O and Θ .

Notice also that although Ω gives us a lower limit for the behavior of our function (i.e., we improve the program so that it calculates fewer instructions), we still refer to the worst case analysis. This is because we feed the program's worst data set and analyze its behavior.

The following table contains the symbols that we have presented above, and their connection with ordinary mathematical icons for comparing numbers. The reason why we use Greek letters instead of the usual mathematical notation is to show that we are dealing with a comparison of asymptotic estimates, and not with the usual one.

Comparison operator for asymptotic estimates	Number comparison operator
The algorithm is o (something)	Number < something
O ( - )	≤ -
Θ ( - )	= -
Ω ( - )	≥ -
ω ( - )	> -

---

: , O , o , Ω , ω Θ , O , , Θ , , Ω .

---