Time & Space Complexity – II

Click here to go to the previous post.

While calculating the space complexity of the algorithm, we established that one variable would take one unit of space.

Space Complexity of Algorithm 2

Click here to view Algorithm 2.

The easiest way to calculate the space complexity is to list out the variables and add 1 for each of them.

Variable     Space
==========   =======
sum            1
i              1
n              1
Arr            n  // since Arr has length n, it would require n spaces.
----------------------------------
Total:         3 + n

S(n) = O(n)

Following the same assumptions and conventions used for time complexity, we can eliminate the constant 3 and say space complexity of the algorithm is of order n.

Let’s move to an algorithm which requires two for loops. We will see why for loop is considered to be expensive.

1. Algorithm AddMatrix (A, B, n)
2. begin
3.   for (i = 0; i < n; i++) {
4.     for (j = 0; j < n; j++) {
5.       C[i,j] = A[i, j] + B[j, i]
6.     }
7.   }
8. end

Time complexity

From algorithm 2, we know that the first line of for loop requires n+1 iterations and anything enclosed in the for loop block runs for n times.

  • Line number 3 and 4, would require n+1 times.
  • But, as line number 4 is inside a for loop (of i), it would also run for n times. So, the total amount of time for line number 4 would become n x (n + 1).
  • Line number 5: It is inside j loop, so it’d take n times and it the j loop itself is inside i loop, so the total would be n x n.
f(n) = (n+1) + n x (n+1) + (n x n)
f(n) = 2n^2 + 2n + 2
     = degree of 2
f(n) = O(n^2)

In this calculation, we have discarded every constant and even n. The reason is, the squared value n will always be way greater than n. See below example:

n = 10            n^2 = 100
n = 100           n^2 = 10000
n = 1000          n^2 = 1000000

Since the time complexity of an algorithm is important for the large set of inputs we can always discard the lower degree.

As in the case of 1000, the value of n^2 is 1000000 (10^6).

Space Complexity

Variable           Space
=========          =========
i, j, n            1 + 1 + 1
A[i,j]             n x n
B[i,j]             n x n
C[i,j]             n x n
----------------------------------------
Total              3 + 3xn^2

S(n) = O(n^2)

The matrices would require n x n units of space as they are the two-dimensional matrix, i.e. n columns and n rows.

The space complexity of this algorithm would be of order 2.

 

As an exercise, calculate the time and space complexity of an algorithm that requires 3 for loops and check what’s the order of time and space complexity.