Why is the time complexity of this code O(x*n*m)? Is this code\'s time complexit

Question

Why is the time complexity of this code O(x*n*m)?

Is this code's time complexity asymptotically tight?

Why?

#include<conio.h>
#include<iostream>
using namespace std;
int main()
{
int a[10][10], b[10][10], c[10][10];
int x, y, i, j, m, n;

cout << " Enter the number of rows and columns for Matrix A::: ";
cin >> x >> y;

// x denotes number rows in matrix A
// y denotes number columns in matrix A
cout << " Enter elements for Matrix A ::: ";
for (i = 0; i < x; i++)
{
for (j = 0; j < y; j++)
{
cin >> a[i][j];
}
cout << " ";
}
cout << " Matrix A : ";
for (i = 0; i < x; i++)
{
for (j = 0; j < y; j++)
{
cout << " " << a[i][j];
}
cout << " ";
}
cout << " ----------------------------------------------------------- ";
cout << " Enter the number of rows and columns for Matrix B::: ";
cin >> m >> n;
// m denotes number rows in matrix B
// n denotes number columns in matrix B

cout << " Enter elements for Matrix B ::: ";
for (i = 0; i < m; i++)
{
for (j = 0; j < n; j++)
{
cin >> b[i][j];
}
cout << " ";
}
cout << " Matrix B : ";
for (i = 0; i < m; i++)
{
for (j = 0; j < n; j++)
{
cout << " " << b[i][j];
}
cout << " ";
}
if (y == m)
{
for (i = 0; i < x; i++)
{
for (j = 0; j < n; j++)
{
c[i][j] = 0;
for (int k = 0; k < m; k++)
{
c[i][j] = c[i][j] + a[i][k] * b[k][j];
}
}
}
cout
<< " ----------------------------------------------------------- ";
cout << " Multiplication of Matrix A and Matrix B : ";
for (i = 0; i < x; i++)
{
for (j = 0; j < n; j++)
{
cout << " " << c[i][j];
}
cout << " ";
}
}
else
{
cout << " Multiplication is not possible";
}
getch();
return 0;
}

Explanation / Answer

#include<conio.h>
#include<iostream>
using namespace std;
int main()
{
int a[10][10], b[10][10], c[10][10];
int x, y, i, j, m, n;

cout << " Enter the number of rows and columns for Matrix A::: ";
cin >> x >> y;

// x denotes number rows in matrix A
// y denotes number columns in matrix A
cout << " Enter elements for Matrix A ::: ";
  
   //Below code will run with complexity O(x*y) which is in computer terms O(n^2)
for (i = 0; i < x; i++)
{
for (j = 0; j < y; j++)
{
cin >> a[i][j];
}
cout << " ";
}
cout << " Matrix A : ";
  
   //Below code will run with complexity O(x*y) which is in computer terms O(n^2)
for (i = 0; i < x; i++)
{
for (j = 0; j < y; j++)
{
cout << " " << a[i][j];
}
cout << " ";
}
cout << " ----------------------------------------------------------- ";
cout << " Enter the number of rows and columns for Matrix B::: ";
cin >> m >> n;
// m denotes number rows in matrix B
// n denotes number columns in matrix B

cout << " Enter elements for Matrix B ::: ";
  
   //Below code will run with complexity O(m*n) which is in computer terms O(n^2)
for (i = 0; i < m; i++)
{
for (j = 0; j < n; j++)
{
cin >> b[i][j];
}
cout << " ";
}
cout << " Matrix B : ";
   //Below code will run with complexity O(m*n) which is in computer terms O(n^2)
for (i = 0; i < m; i++)
{
for (j = 0; j < n; j++)
{
cout << " " << b[i][j];
}
cout << " ";
}
  
   //if the below condition is true then below code will run in
   //Below code will run with complexity O(x*y*m) which is in computer terms O(n^3)
if (y == m)
{
for (i = 0; i < x; i++)
{
for (j = 0; j < n; j++)
{
c[i][j] = 0;
for (int k = 0; k < m; k++)
{
c[i][j] = c[i][j] + a[i][k] * b[k][j];
}
}
}
cout
<< " ----------------------------------------------------------- ";
cout << " Multiplication of Matrix A and Matrix B : ";
      
       //Below code will run with complexity O(x*y) which is in computer terms O(n^2)
for (i = 0; i < x; i++)
{
for (j = 0; j < n; j++)
{
cout << " " << c[i][j];
}
cout << " ";
}
}
else
{
cout << " Multiplication is not possible";
}
getch();
return 0;
}

With above comments Code complexity is as belows:

if(y!=m):
then complexity is O(x*y)+O(x*y)+O(m*n)+O(m*n) = 4*O(n^2) (in computer terms)
which is equal to O(n^2) when value of n is very very large.
else:
then complexity is O(x*y)+O(x*y)+O(x*y)+O(m*n)+O(m*n)+O(x*y*m) = 5*O(n^2)+O(n^3) (in computer terms)
which is equal to O(n^3) when value of n is very very large.

Why is the time complexity of this code O(x*n*m)?

This will be possible only when value of y is equal to m.

If it is not the case then the complexity of the program will be O(n^2).(n does not refer to variable in program) which is because you have two for loops running which can run as large as possible depending on the value of x,y,m,n.

Is this code's time complexity asymptotically tight?

Why?

Yes it is as this program running time complexity will be always between O(n^2) to O(n^3)

Case:

if(y == m)

then it will run with a complexity of O(n^3)

else

it will run with the complexity of O(n^2)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.