analyse the run time of the following code write your analys

analyse the run time of the following code. write your analysis in Big O notation. Assume a big enough value for N

for (int x 0; x n x++) for (int y 0; y n n; y++) System.out.print

Solution

Big O is a notation used in computer science to represent the complexity of the algorithm. It can either be in time or in space. Simply this notation tells how the performance of the algorithm gets affected with respect to the size of the input. This is very very important in analyzing the performance of an algorithm. It is represented with the symbol Big O. Example : O(n), O(log(n)) etc. Usually the complexity of the algorithm is given for all the average case, best case and worst case scenarios. We generally consider the average case complexity.

Eg: Linear search traverses all the elements in the given array to search for a key in the array. So, It traverses atmost n elements (Say size of the array is n) in the array to find the answer in all the best, average and worst case scenarios. So, I can say that time complexity of the linear search is O(n). This means , If for 10 inputs my program takes , say 230 nano seconds to execute, The same program takes 2300 nano seconds to execute for 100 inputs. The function grows linearly in time.

Consider the problem :

There is a nested loop. (Loop inside a loop).

Let\'s split the given code snippet into two parts

for(int x=0; x<n; x++){

System.out.println(\"*\");

}

and

for(int y=0;y<n*n;y++){

System.out.println(\"*\");

}

It is not very difficult to see that the in the first snippet loop gets executed n times. We can say that it has a run time complexity of O(n).

In the second snippet, the loop gets executed n² times. So this part has a run time complexity of O(n²).

If we put both the snippets into a single snippet., We can see that for every iteration in the first loop, The second loop gets executed exactly O(n²) times. So , the whole program will have a run time complexity of

O(n) * O(n²) => O(n³).

So, for 10 inputs we will see 10³ consecutive * s printed. For 100 inputs we can see that 10⁶ * s will be printed.