An algorithm takes 4N+(logN)²+0.001N² steps to execute on an input of size N at the worst case.

Question

a) An algorithm takes 4N+(logN)²+0.001N² steps to execute on an input of size N at the worst case. What is the worst-case asymptotic time complexity (i.e., expressed in terms of the big-O notation)? 

b) Examine the following programming code in Java.

for(int i= 0; i<N*N; i++){
 for(int j= 0; j<N*N; j++){
   sum = 0;
   for(k=0; k<N*N; k++){
    sum += a[i][k]*b[k][j]
   }
   C[i][j] = sum;
 }
}

Determine the worst-case running time of the above program. Give your answer using the big-O notation and explain your derivation.

Summary

In this question, we have to find the worst time complexity. There are two questions, in which we have to tell the worst-case time complexity. 

The time complexity of an algorithm is the amount of time taken by the particular algorithm to execute. And the worst-case time complexity is the maximum amount of time taken by an algorithm given any input of size n. And we present it by Big-Oh (O(n)) notation.

So, in the first question, we are given the steps executed in an algorithm, and we have to find the worst-case time complexity for that. And, in the second question, a program is given and we have to find the worst-case time complexity of it.

Explanation

In the first question, an algorithm takes 4N+(logN)²+0.001N² steps to execute it. Here, we can see that there are three factors as 4N, (logN)², and 0.001N². The factor with the maximum value of it will be the worst-case time complexity of this algorithm. The order will be 4N < (logN)² < 0.001N², so the maximum value factor is 0.001N², and we ignore the constant so the worst-case time complexity of this algorithm will be O(N²).

In the second question, we can see that the program is using nested loops. The innermost loop will run N² times (i=0 to i=N²), the intermediate loop will also run N² times (j=0 to j=N²), and the outermost loop will also run N² times (k=0 to k=N²) in the worst-case. So the overall worst-case time complexity of this program will be N²*N²*N², that is O(N⁶).

Also read, Insertion sort and Quicksort