Algorithm complexity in 5 minutes

What is algorithm complexity, and why is it important to calculate it?

The complexity of an algorithm is a measure of how much more difficult the computational process becomes as the input data increases.

Example:

To iterate through a list of 10 elements, you need to perform 10 iterations. If the list were 1,000 elements long, you’d have to perform 100 times more steps.

And if, in addition, every third element needs to be placed in a new separate list, then you will have to additionally use another 300+ memory cells.

Why calculate the complexity of an algorithm?

If an algorithm requires significant computing power and the volume of input data is large, then the code needs to be optimized as much as possible to speed up the calculations.

What is Big O?

Let’s start with the fact that no one needs to know the exact complexity of an algorithm. Estimation is performed asymptotically, i.e., by answering the question:

If we increase the size of the input data indefinitely, how will the performance of our algorithm change?

This asymptotic estimate is usually performed using Big O or O-notation. It indicates the function that bounds the asymptotic complexity of our algorithm. In other words, if the algorithm’s complexity is O(g), then as the input data size increases, the algorithm’s complexity grows no faster (or even slightly slower) than the function g.

Example:

The complexity of iterating over a collection is O(n). This means that the algorithm’s complexity will grow linearly. Increase the data volume by 10 times, and the complexity will increase by 10 times. Increase it by 100 times, and the complexity will increase by 100 times.

Note: Other notations are also used: omega, small O, etc. But big O is the main and most common instrument.

Basic rules of calculation

1. 1. If the operation does not depend on the amount of data, then it has constant complexity O(1)Examples:
      • Extract the first element of a collection
      • Add two numbers
   2. Adding up the complexity classes leads to the choice of greater complexity
      • If you need to add 2 numbers and then multiply the result by 5, then the complexity of such an operation is O(max(1, 1)) = O(1)
      • If you need to loop through a list (complexity O(N)) and at the end select only the first element (complexity O(1)), then the final complexity will be O(max(N, 1)) = O(N)

Note: In reality, it’s not just the maximum complexity that’s chosen, but rather their summation. For example, O(N + 1). But as the input data approaches infinity, the larger function (N) will overwhelm the smaller one (1). Therefore, only the maximum is chosen.

1. The complexity of IF blocks is calculated using the formula: O(complexity of the condition) + max(O(code in if), O(code in else)).
   

   Example: if the number is greater than N, square it, otherwise iterate over the list arr of length N.

   The complexity of the condition “if a number is greater than N” is O(1), which is a simple comparison. The complexity of “square it” is O(1). The complexity of “iterate over a list arr of length N” is O(N).

   Total complexity: O(1) + max(O(1), O(N)) = O(1) + O(N) = O(N) .

2. When multiplying, the difficulty classes are multiplied
   

   Example:

   – If we loop through the collection and multiply each element by 5, then the complexity will be O(N*1), since the complexity of multiplication is O(1) and we repeat this operation N times.

   – If we loop through the collection and multiply each element by all the others (that is, for each element we loop through the remaining elements again), then the complexity will be O(N*1)*O(N*1) = O(N*N) = O(N^2) .

Main types of complexity

1. Constant O(1)
   • extracting the first element
   • arithmetic operations between numbers
2. Linear O(N)
   • standard for loop
3. Logarithmic complexity O(log N) – only half of the elements are taken at each iteration
   • Divide and Conquer algorithms, such as binary search
4. Linear arithmetic or linearized O(n * log n)
5. Logarithmic complexity O(log N) – only half of the elements are taken at each iteration
   • merge sort
6. Quadratic – O(n^2)
   • double cycle
   • bubble sort

Best, worst, and average difficulty

It’s not always possible to fully estimate the complexity of an algorithm. It depends heavily on the input data: in one case, an algorithm may exhibit linear complexity, while in another, it may exhibit quadratic complexity.

Example: at best, bubble sort has O(N) complexity (when the array is already sorted), at worst – quadratic O(N^2).

Therefore, it’s customary to evaluate at least the best and worst case scenarios. But it’s better to focus on the worst-case scenario. 

The “average” case is also often used as the main characteristic. This is the algorithm’s complexity based on average data. This approach is convenient because the probability of accurately hitting the “best” or “worst” case is low in practice.

Example: You need to find a given element in a list of N elements. In the best case, this element will be the first one, in which case the complexity will be O(1). In the worst case, the desired element will be the last one, in which case the complexity will be O(N). However, on average, you’ll have to make N/2 comparisons, meaning the average complexity is O(N/2) = O(N).

Calculation example

Let’s calculate the complexity of the following code. The FindDuplicates function checks whether the array arr contains duplicates. If so, it returns True; otherwise, it returns False.

• Cycle complexity is O(N)
• The complexity of creating a slice arr[ind+1:] is O(N)
• The complexity of checking in is O(N)
• The complexity of the return operation is O(1)

Total complexity: O(N)*[O(N) + O(N) + O(1)] = O(N^2)

It turns out that if the input data increases by 2 times, it will be necessary to perform 4 times more operations.