thaveethu gce thaveethu gce - 1 year ago 36
Java Question

How to calculate Time Complexity in nested for loop?

What is the time complexity of the following snippet? and could you explain it?

for(int i=0;i<n;i++){
for(int j=0;j<=i;j++){
//print something
}
}

Answer Source

The outer loop has n iterations.

The inner loop has i+1 iterations for each iteration of the outer loop.

Therefore the total number of iteration of the inner loop is:

1 + 2 + 3 + ... + n

which is equal to

n*(n+1)
-------
   2

This is O(n^2)

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download