Calculate time complexity of below code in O-notation

When i attended interview in investment banking domain companies such as Goldman Sachs, JP M&C, Morgan Stanley, etc. Most of the questions based on the performance of the code.

Performance is calculated mostly based on the Time complexity.

Time complexity of an algorithm signifies the total time required by the program to run to completion. The time complexity of algorithms is most commonly expressed using the big O notation.

Here i have given some example and detailed explanation of the code


1) Performance of traversing given integer array with the help of for loop ..

Code:

int a[] = {23,45,66,67,78,90};

for(int i=0;i<a.length;i++ {
     System.out.println("  value :"+a[i]);
}

Explanation:

The above for loop iterating the entire array with the help of array length, So for loop will continue to execute till the end of the loop. i.e 90 (last element of the arrray).  So the performance in O-notation is O(6), where 6 is length of the array. In most generic way , O(N) , where Nis the number of elements in array.

Answer:
     Time complexity :-   O(N).  

2) Performance of loop inside another loop.

Code:

for(int i=0;i<N;i++ {
    for(int j=0;j<N;j++ {
       System.out.println(" hi");
    }  
}

Explanation:

The above code consists of one outer loop and one inner loop. Based on one condition of outer loop , inner loop will continue to run. i.e For every one element from outer loop, inner will execute N times.

Lets say N=3, When i=0(first valid condition), inner loop will excute three times(j=0,1,2) and for i=1(second valid condition), inner loop(j=0,1,2) and third(i=2, j=0,1,2); So totally 9 times the block will get execute. So the performance is O(9)  = O(3^2) i.e O(N^2).

Answer:
    Time Complexity:- O(N^2)

Click to Read more Algorithms and its performance