Time & Space Complexity – I

In simple words, time complexity is the amount of an algorithm takes to execute, and the space complexity is the memory used. In general, if you have ever studied the time and space complexity of algorithms, the one thing that we remember is: for loops are bad.

In this first part of the series of analysis of algorithms, I am going to give a refresher on finding the time and space complexities of simple algorithms.

Algorithm 1:

1. Algorithm swap (a, b)
2. begin
3.   temp := a
4.   a := b
5.   b := temp
6. end

A simple algorithm for swapping two numbers. The three steps of the algorithms are:

  1. assign the value of variable “a” in a “temp” variable.
  2. assign the value of variable “b” in variable “a”.
  3. assign the value of “temp” in variable “b”.

To calculate time and space complexity, we make some assumptions:

  1. Every arithmetic evaluation takes 1 unit of time.
  2. Every variable occupies 1 unit of space, called word.

Time Complexity
Each step takes 1 unit of time, so in total, 3 units of time. The time complexity of an algorithm is expressed as a function of “n”.

f(n) = 3

Space Complexity

Each variable will take 1 unit of space. The space complexity of an algorithm is expressed as a function of “n” represented by the letter S.

Algorithm 2:

1. Algorithm getSum (Arr, n)
2. begin
3.  sum = 0;
4.  for (i = 0; i < n; i++) 
5.  {
6.     sum = sum + Arr[i]
7.  }
8.  return sum  
9. end

An algorithm to add numbers present in an array.

Time Complexity:

Line numbers 1, 2, 5, 7, 8, and 9 will not be considered for calculating time complexity.

Line number 3 and 6 would require 1 unit of time.

Line number 4 has 3 parts,

  1. “i = 0” requires 1 unit.
  2. “i < n” would require n + 1 comparison (n satisfied, and 1 not satisfied, where the for loop will exit.)
  3. Each i++ would need 1 unit time, but since the length of the array is n, it would require 1 x n unit of time.

If we see the third part of the for loop and line number 6, we would realize line number 6 will also be executed n times. So we can write the following expression:

f(n) = 1 + 1 + (n+1) + n + n
f(n) = 3 + 3n 
/**
 * 3 is a constant number and can be a very small number when compared to n,   * so we can ignore the constant 3. Same goes for the multiplier of n.
 */

// it can also be said that the degree of the expression is 1, hence

f(n) = O(n)

This is read as,

time complexity, which is a function of n, is the order of n for this algorithm.

In the next post, we will calculate the space complexity of this algorithm and two more algorithms which will have more than one for-loop.