Please explain why on both questions 1) What is the asymptotic time complexity o
ID: 3564576 • Letter: P
Question
Please explain why on both questions
1) What is the asymptotic time complexity of the following piece of code? Use big-O notation.
for (int i = 0; i < N ; i++)
for ( int j = 0; j < N; j++)
A[i, j] = B[i, j] + C[i, j];
2) Assume N and M are initialized integers, student is an array of integers and average is an array of float. What is the asymptotic time complexity of the following piece of code? Use big-O notation.
float total = 0;
for (int i = 0; i < N; i ++)
{
cin >> data;
if ( data % 2 == 0)
total =total + data;
if sum >= 1000
break;
}
for (int k=0; k < M; k++)
{
if (student[k] == id)
average[k] = total/i;
}
Explanation / Answer
answer
for (int i = 0; i < N ; i++)....................................This will be executed N+1 times
for ( int j = 0; j < N; j++)......................For each i This will be executed N+1 times so totsl of Nx(N+1)
A[i, j] = B[i, j] + C[i, j];............This will be executed N(N) times
So the number of operations required by this loop are:
N+1 +Nx(N+1) +NxN=2N2+2N+1
so it has asymptotic time complexity of O(2N2+2N+1) which is O(N2)
(2)
float total = 0;..................................This will be executed only once
for (int i = 0; i < N; i ++)....................This will be executed N+1 times
{
cin >> data;..................................This will be executed N times
if ( data % 2 == 0).......................For worst case This will be executed N times
total =total + data;......................For worst case This will be executed N times
if sum >= 1000......................For worst case This will be executed N times
break;...................................
}
for (int k=0; k < M; k++).................... This will be executed M+1 times
{
if (student[k] == id).................... For worst case This will be executed M times
average[k] = total/i;...................For worst case This will be executed M times
}
So the number of operations required by this loop are:
1+(N+1)+4N+(M+1)+2M=5N+3M+3
so it has asymptotic time complexity of O(5N+3M+3) which is linear so we can write it is O(n)