Introduction to Algorithm Complexity Analysis (Part 2)

From the translator: this text is given with minor abbreviations due to places of excessive "chewed up" material. The author absolutely rightly warns that certain topics may seem too simple or well-known to the reader. Nevertheless, to me personally this text helped 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 parts, of which there will be a total of four.
I (as always) will be extremely grateful for any comments in PM on improving the quality of translation.

Published earlier:
Part 1

Complexity

From the previous part, we can conclude that if we can discard all these decorative constants, then it will be very simple to talk about the asymptotic behavior of the function for counting program instructions. In fact, any program that does not contain loops 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 1to ngives asymptotics f( n ) = n, because before and after the cycle it executes an unchanged number of commands, while the constant number of instructions inside the cycle runs nonce.

Guided by such considerations is less tedious than reading instructions each time, so let's look at a few examples to consolidate this material. Next php-program checks whether a given value is contained in an array of Asize n :

This method of finding a value inside an array is called linear search . This is a valid name because the program has f( n ) = n(which means “linear” more precisely, we will cover in the next section). The instruction breakallows 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 Adoes not contain a given value at all. Therefore, f( n ) = nas before.



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 to see if a vector (a sort of array) of Asize contains ntwo 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 give us the asymptotics of the form f( n ) = n² .

---

Practical recommendation : simple programs can be analyzed by counting the number of nested cycles in them. A single loop in niterations gives f( n ) = n. The cycle inside the cycle is f( n ) = n² . The cycle inside the cycle inside the cycle is f( n ) = n³ . Etc.

---

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

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

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

---

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

---

Now let's switch to the interesting notation used by theorists. When we find out the exact asymptotics f, we say that our program is Θ( f( n ) ). For example, in the above examples of the program Θ( 1 ), Θ( n²) and Θ( n² ) , respectively. Θ( n )pronounced as "theta from n". Sometimes we say that f( n )(the original function of counting instructions, including constants) is Θ( что-то ). For example, we can say that f( n ) = 2nis a function that is Θ( n ). In general, nothing new. You can also write that 2n ∈ Θ( n )what is pronounced: “two n belongs to theta from n”. You should not be confused by such a notation: it just says that if we calculate the number of commands necessary for the program, and it will be equal2n, then the asymptotic behavior of this algorithm is described as n(what we find by discarding the constant). Having this system of notation, we give a few true mathematical statements:

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

By the way, if you decided to exercise 1 of the first part, then this is his correct answer.

We call this function (i.e. what we write Θ( здесь )) the time complexity , or simply the complexity of our algorithm. Thus, algorithm c Θ( n )has complexity n. Special names also exist for Θ( 1 ). Θ( n ), Θ( n² ) and Θ( log( n ) )because they are very common. They say that Θ( 1 )- an algorithm with constant time , Θ( n )- linear , Θ( n² ) - quadratic , and Θ( log( n ) )- logarithmic (don’t worry, if you still don’t know what the logarithm is, 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 difficult to find out the exact behavior of the algorithm in the way that we considered above. Especially for more complex examples. However, we can say that the behavior of our algorithm never crosses a boundary. This makes life easier, since we may not even have a clear indication of how fast our algorithm is, even if we ignore the constants (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 learning algorithms is sorting. An array of Asize is given .n(sounds familiar, right?), and we are asked to write a program to sort it. The interest here is that such a need often arises in real systems. For example, a file browser needs to sort files by name to make it easier for the user to navigate them. Or another example: in a video game, the task of sorting 3D objects displayed on the screen according to their distance from the player’s point of view in the virtual world may arise. Purpose: to determine which of them will be visible to him and which will not (this is called the Visibility Problem ). Sorting is also interesting because there are many algorithms for it, some of which are worse than others. This task is also simple to define and explain. 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

Here is a completely inefficient way to implement array sorting in Ruby. (Of course, Ruby supports sorting arrays using the built-in functions that you should use. They are undoubtedly faster than the code above, presented solely for illustration.)

This method is called selection sorting . First there is the minimum element of the array ( ain the code above. The minimum is indicated as m, and its index - as mi), which is placed at the end of the new array (bin our case) and is removed from the original. Then, among the remaining values, the minimum is again found, 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 a new array, which will mean the end of the sort. In our example, we have two nested loops. The outer loop “runs” nonce, and the inner loop once for each element of the array a. Since it initially ahas nelements and at each iteration we delete one of them, first the inner loop “scrolls” nonce, then n - 1, n - 2and so on, until the last iteration the inner loop passes only once.

If we consider the amount1 + 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 will change the program (you can mentally, without touching the code) to make it worse than it is, and then derive the complexity for what happened. Then it can be confidently said that the original program works either badly or (most likely) better.

Now let's think about how we can change the program in order 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 evaluation makes sense for the original program. Obviously, we can change the inner loop of a program by making it computentimes 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, our new algorithm will have Θ( n²) , because we get two nested loops, each of which runs exactly nonce. And if so, then the original algorithm has O( n² ) . O( n^{2 is} ) pronounced "big O from nsquared." This suggests that our program is asymptotically no worse than n² . She will work better or better. 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 just a little bit worse. It’s about how to add useless instructions to the beginning of the program. This will only change the constant in the instruction counting function, which we will ignore in the asymptotics. Thus, Θ( n²) for the program is O( n^2, ) 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 a Θ( n )program is just a cycle forthat runs nonce, we can make it worse by adding another for, also repeating ntime inside . This will give a program with f( n ) = n² . Summarizing: any program withΘ( a )is O( b )at bworse than a. Note also that the change does not have to make sense or create code similar to the original. 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 the instructions, not to solve the problem.

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





Since the Оcomplexity of the algorithm is the upper limit of its real complexity, which, in turn, is displayed Θ, sometimes we say that it Θgives us an accurate estimate . If we know that the border we found is not accurate, then we can use the lowercase оto indicate it. For example, if an algorithm is Θ( n ), then its exact complexity is n. Therefore, this algorithm O( n )and O( n² ) at the same time. Since the algorithm Θ( n ), it O( n )determines the boundary more accurately. And O( n² ) we can write as о( n² )(pronounced: “small o of n squared”) to show what we know about the laxity 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 Ocomplexity of the algorithm is easier than its Θcomplexity.

---

By now, you might already be confused with all these new notations, but let's get to know two more characters before moving on to the next examples. Above, we changed our program to make it worse (increased the number of instructions and, thus, the execution time), than created O-notation. Оtells us that our code will never run slower than a certain limit. From this we get the basis for evaluation: is our program good enough? If we do the opposite, making the existing code better , and find the complexity of what happens, then we use the Ω-notation. Thus,ΩIt gives us complexity, which our program cannot be better. 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, saying that the algorithm is Ω( n³ ) means that the algorithm is no better than n³ . He may be Θ( n³ ) , or Θ( n⁴ ) , or worse, but we will know the limit of his "goodness." Thus, Ωit gives us a lower bound on the complexity of our algorithm. Similarly ο, we can write ωif we know that this limit is not strict. For example, Θ( n³ ) algorithm is ο( n⁴ )and ω( n² ) . Ω( n )pronounced “omega big from n”, while ω( n )pronounced “omega small from n”.



The reason that we use Oand Ω, instead Θ, is that we can not be sure of the accuracy we found the boundaries or simply do not want to dig deeper into the algorithm.

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

Note also that although Ωit gives us a lower limit to 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 worst data set into the program and analyze its behavior.

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

Comparison operator for asymptotic estimates	Number comparison operator
The algorithm is o (something)	Number < of something
Algorithm is O (something)	Number ≤ something
Algorithm is Θ (something)	Number = Something
Algorithm is Ω (something)	Number ≥ of something
Алгоритм является ω( что-то )	Число > чего-то

---

Практическая рекомендация: несмотря на то, что все символы O, o, Ω, ω и Θ необходимы время от времени, O используется чаще всего, поскольку его проще найти, чем Θ, и оно более полезно на практике, чем Ω.

---