# 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 ^{6})**.

Also read, Insertion sort and Quicksort