There is an algorithm of complexity O(n*Log(n)) , there is a computer with a 2.1GHz processor. Problem: how to calculate the running time of the algorithm on the machine if we know N ?

As I understand it, the complexity function is needed just to characterize the running time of the algorithm.

When calculating the time of the algorithm based on the complexity function, I’m confused by the fact that such things are not taken into account:

 a = a+b;// O(1) 1с b = b+1;// O(1) 1с

Total execution time of these operations is 2c, the complexity function is O (1). According to the function of complexity, somehow it is not possible to get the execution time of the algorithm. Is it possible, in principle, to determine the running time of an algorithm, knowing its complexity?

  • five
    The running time will be very dependent on the specific processor. The same operations are different processors running on the same frequency are performed at different speeds. And not only the operation plays a role, but also a combination of operations. Two independent operations performed in a different order lead on modern processors to different execution times due to internal optimization in processors. And the clock frequency is very far from it. The complexity function provides only a remote understanding of the number of operations and can only be used for comparative purposes to evaluate algorithms - Mike

2 answers 2

It's impossible. The "complexity function" O(f(N)) , as you called it, answers the question of how fast the number of operations of the algorithm ( f(N) ) grows when N goes to infinity. That is, for example, if sorting has complexity O(N^2) , then by doubling the size of the array, you get a quadrupling of the number of operations necessary for sorting, provided that N is a very large number. This function has no relation to the operation time. O(1) Means that the speed of the function does not depend on the size of the input parameter N , while the operation time can be from zero seconds to billion years (and more).

You should also understand the difference between the algorithm and the program that implements it. The complexity of the algorithm is one thing, but the speed of the program is quite another. These values ​​may be related, but not always in an obvious way.

Details (but very complex) can be read here .

    Complexity is not about time itself, but about how it will change with change in n . You can measure the running time of your program on the target machine for some specific (for example, small) n , and knowing the complexity, estimate how long it will take to work with other (for example, very large) values.