How to calculate Time Complexity in nested for loop?

Question

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 1

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)

Answer 2

Whenever you face a question of calculating time complexity, just look for how many times you are going to do the work.

Here, in your question, whatever the work you are doing, lets say printing something, you are going to do it for the the number of times of outer loop, which itself runs for n length. hence, you will do the work for 1+2+3+....n times which becomes n*(n+1)/2 times.

Hence, it will simply be O(n^2)

Answer 3

1. For i=0, inner loop runs 1 time
2. For i=1, inner loop runs 2 times
3. For i=2, inner loop runs 3 times ...

n-1. For i=n-1, inner loop runs n times

So, total time = 1 + 2 + 3 +....+ n

n*(n+1)/2

and represented as O(n^2)

Answer 4

Time complexity is Big O of n square i.e. O(n^2)

1. For outer looper, it is n

2. Cost of inner loop is 1 + 2 + 3,...n-2, n-1, n

So total cost is O(n^2)

Answer 5

Quadratic Function (Quadratic Run Time)

An algorithm is said to be quadratic if

the main reason why the quadratic function appears is the nested loops, where the inner loop is performing a linear number of operations n and the outer loop is also performing a linear number of operations n, thus, in this case, the whole algorithm perform operations.

n is the number of elements you would have in any given array.

if the number of elements in your array is 10, this means it would take 10 * 10 = 100 operations to finish the execution of your logic.

A good example is to check how many a single item occurred in a list, this required comparing each single element in the list with all the element in the list including itself.

quadratic function graph:

I have an old BigO notation notes that covers the 7 most famous run time complexities see if this will help BigO