O(n) – Algorithms/Computational complexity, may I help you?

When I had started to learn Software development I learned about computational complexity. Since this time I did not use it any more. But, it is good to refresh your knowledge sometime (and why not to avoid failing an interview).

What is complexity?

Complexity is a way to evaluate how an algorithm will evolve if we change the size of data it treats. With complexity, you cannot know the time the application will take to work! You may know the performance and be able to compare the efficiencies of two algorithms with their complexities.

Let see an simple example, a colleague and you create an algorithm to find the min and the max value in an array. Here is your implementation :

void printMinMax(int array[], int size){
int min = MAX_INT, max = MIN_INT;
    // Look to each values
    for(int index = 0 ; index < size ; ++index){
         // Check min
         if(array[index] < min) min = array[index];
         // Check max
         if(array[index] > max) max = array[index];
    }

    std::cout << "Min="<< min << "   Max=" << max << std::endl;
}

Your colleague does something like :

void printMinMax(int array[], int size){
    int min = MAX_INT, max = MIN_INT;
    // Look to find the min
    for(int index = 0 ; index < size ; ++index){
        if(array[index] < min) min = array[index];
    }
    // Look to find the max
    for(int index = 0 ; index < size ; ++index){
         if(array[index] > max) max = array[index];
    }

    std::cout << "Min="<< min << "   Max=" << max << std::endl;
}

After seeing the solution you may think “My solution is the best!”, yeah you won. But let’s describe more in details.
In your solution, there is “size” loop, the number of loop is the size of the array. If your solution takes 1s to work with a 1000 values array. It will take 2s for a 2000 values array. I hope that with this argument you understand why your algorithm has a complexity of O(n). With mathematical terms, we can say that the complexity is linear (y=ax+b).

So here, Total_time = n * time_of_one_loop (with n the number of elements).
In the second solution, we do two loops. So, if it takes 2s for 1000 values, it will take 4s for 2000 values (multiple by 2). The complexity is also linear : O(2n).

And we can say that Total_time = n * time_of_one_loop + n * time_of_one_loop = 2 * n * time_of_one_loop

So your solution is better! You can see it on the graph. As I said, we cannot know the real time because it depends on the time on what you do into a loop. But we can see the difference of the two algorithms and how they evolves.

How to know the complexity

As describes above, when you are doing a simple loop the complexity is O(n), when you are doing two loops O(n+n) = O(2n) and so on.

Now, imagine a loop into a loop (for example to look into a matrices) :

void printMinMax(int array[][], int m, int n){
int min = MAX_INT, max = MIN_INT;
    // Look to each values
    for(int index = 0 ; index < m ; ++index){
         for(int index2 = 0 ; index2 < n ; ++index2){
              // Check min
              if(array[index][index2] < min) min = array[index][index2];
              // Check max
              if(array[index][index2] > max) max = array[index][index2];
         }
    }

    std::cout << "Min="<< min << "   Max=" << max << std::endl;
}

Lets first look at the second loop. Its complexity is O(n) like previous examples.
And what about the first loop? We can badly say O(m * O(n)) but we never put a “O” into another, so we say O(n*m).
Imagine m = n, then the complexity will be O(n^2). So the time of the application will increase with the square of the elements.

Imagine that you have a algorithm that takes every time the same time whatever the array you work on.

void Delete(int array[]){
     delete [] array;
}

Well, by convention we say that the complexity is : O(1)

The last interesting complexity is O(log2 n). This complexity is present in algorithm like dichotomy research. In this algorithm there is an array with sorted values, for example [0 1 2 3 4 5 6 7 8 9]. The algorithm try to find 3 (for example).
It will look the middle of the array (4), because it searches 3 so the value is on the left. It looks in the middle of the left middle (2) what we search is bigger so we divide by two again and we look in the right part. We find 3.
As you can feel, as the number of elements grows the number of loop (array division) grows but not in a linear way. And there is no relation like n/2.
Here is examples of relation :
elements (n) > division (log2 n)
10 > 3
100 > 7
1000 > 10

If you look to famous algorithms properties you may find best complexity, worse complexity and average complexity.

Several (famous) examples

The most famous examples come from sorting methods (we look only to the average).

Bubble sort : O(n^2)

Quick sort : O(n log n)

Binary tree sort : O(n log n)

You can find more on internet and you can also find some resources about memory complexity.