Using the Big-Oh notation, estimate the execution time of the following algorithm: (13 Marks)

for j = 3 to n-1  
  for k = 2 to n  
  print(j*k)  
  end  
end 

****Is my answer and approach for this question worth 13 marks, else what you do expect? ****

for (j = 3 to n-1)             //the loop runs n number of times and does O(n-1) work per iteration. 
     for (k = 2 to n)            // runs from 2 to n number of times thus, O(n) 
             print(j*k)          // this is constant thus O(1) 
      end  
end 
 
let n=20. j will run from 3 to (20-1). k will run from 2 to (20).  
And  
print (16*19) ??confuse here ?? 
Total=  O(n-1)+O(n)+O(1)    *Drop constant & take highest  
priority 
= O(n)*O(n)  
=O(n2) <---- 

What is meant by the complexity of an algorithm? ((is it worth 2 marks ??)) –It is a way of showing how the time taken to execute an algorithm increases with the increase of input size. How do we measure complexity of an algorithm? ((is it worth 2 marks ??)) There are 2 types of complexity:

1. Time Complexity=the number of steps require to run an algorithm.
2. Memory complexity= the number of memory to run an algorithm.

Give four reasons to analyse the efficiency of an algorithm. (is it worth 4 marks ??) –We consider the worst case scenario because we must know the maximum time it takes to run the algorithm. –The best case scenario or any average case scenario will not help because they will never give the maximum time. –So, our concern is to know what the upper bound is and this way we can evaluate the performance of an algorithm. –Time complexity gives an estimate of how an algorithm performs as the number of items grows, that is, how well an algorithm will scale

Calculate the time complexity of the following method/function based on the number of comparisons only. (13 Marks).

public static Matrix Multiply(Matrix A, Matrix B){        
Matrix temp = new Matrix(A.rows, A.columns);               // constant time, O(1) 
if (A.rows != B.columns){                                   /* 
      System.out.println("Matrix dimensions do not match"); **constant time, O(1)* 
      System.exit(0);                                        */ 
}  
        for (int r = 0; r < A.rows; ++r)                  // O(n) 
                 for (int c = 0; c < A.columns; ++c){  // O(n) 
                     temp.Data[r][c] = 0;               // O(1) 
                 for (int k = 0; k < A.columns; ++k)  //O(n) 
                  temp.Data[r][c] = temp.Data[r][c] + A.Data[r][k] * B.Data[k][c];  //O(1) 
                  } 
                  return temp;   //O(1) 
                   } 
           } 

1. Matrix temp is assigned matrix A row and columns thus, O(1)
2. everytime there is a comparison statement, print and then the program stops. Thus, O(1)
3. The time it takes to perform this for loop is proportional to the size of the array thus, O(n) or O(A.rows)
4. For loop will run until r<n thus, O(n) — O(A.columns)
5. Assignment statement thus, O(1)
6. For loop will run until r<n thus, O(n) — O(A.columns)
7. Assignment statement thus, O(1)
8. Return temp thus, O(1)

Calculate the time complexity of the following algorithm based on the number of comparisons only. (12 Marks)

  For i = 2 to n                            // O(n) 
          If x > y then                /* 
          Print y                       *constant time, O(1)*/ 
          End                                
      For j = 2 to n                      //O(n) 
           If z > j then            /* 
           Print z                    * constant time, O(1)*/ 
           End                            
          For k = 2 to n           // O(n) 
               If w > k then     /* 
               Print w            * constant time, O(1)*/ 
              End  
          End  
     End  
 End 

1. the loop runs n number of times and does O(n) work per iteration.
2. Everytime there is a comparison statement, print and then the program stops. Thus, O(1)

Total = (O(n)+O()) + (O(n)+O()) + (O(n)+O()) ignore constants, take highest priority = O(n) O(n) O(n) =O(n3) <—-