Algorithm time complexity

While interviewing people for a Software Engineer position in different countries, I’ve noticed that pretty often any question related to algorithms execution complexity (whether it is time or space complexity) is rarely being answered correctly. Truth be told, there are very rare occasions at any company when an engineer needs to develop a new (or a combination of existing) algorithm for some business use case, however, very often we need to either reuse existing algorithm or even underlying data structure that should fit our data as well as requirements. In this article, we will look at the time complexity of an algorithm and all related terms a person could face with.

Let’s start with a definition of time complexity itself and why we care about “time”. Time complexity is indeed a measure of time that takes an algorithm to finish. However, in real-world scenarios, we may assume that every primitive operation (for example, read variable’s value) is fixed in time, and the amount of parallel operations per second is derived from hardware architecture, as well as it can be scaled up using more up to date hardware. So, it may be hard to correctly predict the algorithm’s execution time because it is very related to the computer on which this algorithm is being executed. So, we may interpret the algorithm’s time complexity as the number of operations that are required to be executed.

The algorithm’s time complexity is usually interpreted as the number of operations to be executed for the algorithm to finish.

For example, let’s consider a simple algorithm that calculates the sum of elements of a given array of integers. To make it even simpler we assume that reference to the array is always not null, the array is not empty and we would not face integer overflow when calculating sum (hence return type is an integer as well).

private static int arraySum(final int[] intArray) {
     int sum = 0;
     for (int j : intArray) {
         sum += j;
     }
     return sum;
 }

Function growth order

This algorithm goes through all the elements of a provided array and adds every next element to sum a variable which is returned as a method result. It is easy to see that amount of operations depends on the number of elements in the array – for 5 elements we will do 5 additional operations, for 1000 it would be 1000 operations. Mathematically speaking we may assume that for an input array of size N we would need N operations, so our algorithm complexity is linear. This is also called a function growth order which describes how function (number of operations) grows based on its input size.

There are multiple standard function growth orders (from least to most growing):

• Constant – no dependency from input
• Logarithmic – logN
• Linear – N
• Linearithmic – N ∗ logN
• Polynomial – N²
• Exponential – 2^N

As you can see, for example, the linearithmic function has lesser growth than the linear function till N = 10, however, it grows faster afterward. As well, there is almost no difference between polynomial and exponential functions till about N = 20.

Function growth order describes how fast function grows when input value rises.

Tilde approximation

Now let’s assume that we need to calculate the sum of a given array but don’t take into account the last 2 elements (for the sake of simplicity we would not handle cases where the array is empty or has too few elements). The number of operations would be N − 2. For a big amount of elements in the array, we could say that there is no significant difference between N and N − 2 operations. This assumption is called tilde approximation, mathematically we can reference our array sum approximation as N – 2 ~ N for N → ∞. Such approximation can be used only to drop part of algorithm complexity that is of lesser growth order. For the N − 2 case, N is linear and 2 is constant, so we can drop 2. In the case of having 2 variables like N + M, we can’t make such an approximation because both variables are growing independent of each other.

In the example above for complexity N − 2 both tilde approximation and order of growth are the same – N. There are, however, lots of cases where they would be different. If we calculate the sum only for half of a given array, the number of operations would be N / 2. The order of growth would still be N in this case as the dependency on input data is linear. However, tilde approximation would still be N / 2 because there is no lesser growth order part in this amount of operations and, hence, nothing to simplify.

Tilde approximation excludes less significant growth orders of a function.

Algorithm behaviors in different cases

Another very important quality of an algorithm is how it behaves when passing different input data. Let’s consider the brute-force algorithm for finding a character’s first occurrence in a string and returning the position of this character within a given string.

private static int indexOf(final char character, final String str) {
     for (int i = 0; i < str.length(); i++) {
         if (character == str.charAt(i)) {
             return i;
         }
     }
     return -1;
 }

If we are looking for the character ‘h‘ in the word ‘holiday‘, we would find it immediately on position 0. On the other hand, to get a character ‘y‘ in the same word we would need to go through all the characters of a given string. This means that in the best-case scenario we will find a requested character in 1 operation, in a worst-case scenario we would need to perform N operations. For the average case, we may assume that on a big number of attempts average complexity would be N / 2. Those complexities fall under different notations that are widely known and used to estimate the performance of an algorithm.

• Big Omega notation – Ω – best-case scenario
• Big Theta notation – Θ – average case scenario
• Big O notation – O – worst-case scenario

The algorithm complexity of average or one of the edge cases is usually interpreted in the following. O(N²) means that the time complexity of an algorithm in a worst-case scenario is N². Ω(2) – time complexity in the best-case scenario of a given algorithm is constant.

That’s it for this article, hope now time complexity and all related terms are much clearer. I’m also working on an algorithm space complexity article which should be available soon.