Time Complexity Examples 2

For Complete YouTube Video: Click Here

In this class, we will try to understand Time Complexity Examples 2.

The have already discussed an example to find the time complexity in our previous class.

To understand how to find an algorithm’s time complexity, consider the image below.

The above image shows the algorithm for matrix addition.

First, we will understand the algorithm and then find an algorithm’s time complexity.

The outer for loop iterates for m + 1 times.

Each time we come into the loop the inner loop will iterate for m(n + 1) times.

For each iteration of the inner for loop a row values will be added.

The values of m and n represents the number of rows and columns.

The expression c[i, j] = a[i, j] + b[i, j] will add the values in the matrix A nd B and will will stored in C.

The expression c[i, j] = a[i, j] + b[i, j] will be executed for mn times.

The number of times each step of the algorithm is executed is shown below.

The time complexity of the algorithm is m + 1 + mn + m + mn = 2mn + 2m + 1.