# Understanding Time Complexity (N²)

There is a nested “for” loop and for every iteration loop increments by one. Now, if we are asked about the time complexity of the above scenario, we give a quick answer O(N²) or Theta(N²) or Omega(N²). Yes, the answer is right. But, if you would like to know ‘**Why**’ or ‘**How**’ is it ‘N²’, then this is the article for you.

Readers who already knew it, feel free to correct me if I am sliding out in a wrong way.

The output of the above program is -

Time Complexity:It is the computational complexity that describes the amount of time a computer takes to run an algorithm. Time complexity is commonlyestimatedby counting thenumber of elementary operationsperformed by the algorithm.

As per the definition we should focus on the number of elementary operations in a program. Here inside the nested “for” loop, there is only one operation is taking place i.e., **System.out.println(“*”).**

Now if we count the number of **System.out.println(“*”) **statement executes, this will be the time-complexity.

From the output of the above program, counting the **number of stars **defines the count of **System.out.println(“*”) **execution. For input ‘N** = 5’, number of stars** = 1+2+3+4+5 = 15. This calculation can be formulated as sum of ’n’ numbers i.e., **N(N+1)/2.**

From the above, we deduce **System.out.println(“*”) **executed 15 times. Consider this as LHS. Now if we substitute ‘**N = 5**’ in N², we get the value 25. Consider this as RHS. Though the comparison between LHS and RHS fails, we consider **N² **as solution for the above program**.**

Simplify ‘**N(N+1)/2’ **further, we get **(N²/2+N/2). **Since we consider only higher power variable and neglect constants, we deduce the solution to **N²**.

So, the notation **N² **is just an **estimate **but not accurate measurement.

*Feel free to share your views on this article*

*Thank you !*