Time and Space complexity

Welcome back to yet another blog post. Hope you are doing well. In this post I have written down the time and space complexity of different data structures and algorithms for reference.

log₂n < n < nlog₂n < n² < 2ⁿ < n!

log₂n is one of the best while n! is one of the worst.

Table of Content

• Time and Space complexity
  • Common Data Structures
  • Array Sorting Algorithms
• Growth rate
• Common growth rates
• Compare growth rates
• Determine time complexity

Time and Space complexity

Color code from best to worst complexity.

Common Data Structures

WORST complexity

Array Sorting Algorithms

Growth rate

It is the rate at which the cost of the algorithm grows as the size of its input increases.

For example, consider the following code which prints the characters of a string.

str = "Hello World!";
for(i = 0; i < str.length; i++) {
  print(str[i]);
}

There are total 12 characters in the above string str.

Now, let us look at the operations being performed in the above code snippet.

• The variable str is assigned the string value.
• The loop variable i is initialize with value 0.
• The for loop condition is checked.
• If the condition is valid then the character is printed.
• After each loop the variable i is incremented by 1.

Total operations is 1+1+13+12+12 i.e., 39 times.

If there are n characters in the string str then the growth rate of the above code will be the following.

So growth rate of the above code is 1+1+(n+1)+n+n i.e., 3n+3.

Common growth rates

From the above growth rate table we can safely say that log₂n is the best while n! is the worst.

Compare growth rates

In this section we will compare the growth rates and check with of the given functions is growing quicker.

To compare growth rates we can go through the following steps.

• Remove common values from both the functions.
• Take log of both the functions.
• Replace the input n with a very large value.
• Compare the value.

Exercise 1

So, f(n) > g(n)

Exercise 2

So, f(n) < g(n)

Exercise 3

So, for a smaller value of n we get f(n) < g(n).

Now, let us try for higher value of n.

So, for larger values of n we get f(n) > g(n).

Determine time complexity

In this section we will find the time complexity of some of the code snippets.

Example 1: loop

for(let i = 0; i < n; i++) {
  console.log("Hello");
}

This code will execute n times so its time complexity is O(n).

Example 2: nested loop

for(let i = 0; i < n; i++) {
  for(let j = 0; j < n; j++) {
    console.log("Hello");
  }
}

The outer loop will execute n times. And for each outer loop execution the inner loop will execute n times. Therefore the total execution time is n² and time complexity is O(n²).

Example 3: nested loop

for(let i = 0; i < n; i++) {
  for(let j = 0; j < i; j++) {
    console.log("Hello");
  }
}

The outer loop will execute n times.

During the first loop, when i=0, the inner loop will not execute. Then onwards, for every i, the inner loop will execute i-1 times.

So, total execution time is n(n-1) i.e., n²-n.

Therefore, the time complexity is O(n²).

Example 3: logarithmic

for(let i = 1; i < n; i*=2) {
  console.log("Hello");
}

From the above code, the value of i which increase like the following.

i = 1, 2, 4, 8, 16, ..., n

Or,

i = 2⁰, 2¹, 2², ..., 2^k

The loop will end when 2^k = n.

Taking base 2 log of both sides we get log₂2^k = log₂n

Or,

k = log₂n

The console.log statement will be executed log₂n times.

So, time complexity of the above code snippet is O(log₂n)