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 commonly estimated by counting the number of elementary operations performed 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 !