Search code examples
algorithmperformancetimingnotation

How is the running time calculated for nested "for" loops?


Recently started with this so need your help, Lets say you have nested for loops as shown below, both ranging from 1 to n, how does one calculate the running time for the same in terms of Big O, Theta, Omega?

for(i=1; i<n; i++) {
    for(j=1; j<n; j++) {
       //some piece of code
    }
}

Solution

  •  for(i=1; i<n; i++) {
         for(j=1; j<n; j++) {
           //some piece of code
          }
      }
    

    So let's look closer at this piece of code. Say we have a set of 10 items (n) and we execute these loops one by one. First it has to pass the i loop. he'll pas it for 1, then that 1 goes into the second loop 10 times before 1 becomes 2. In total it has to pass loop 100 times before reaching the end. In big O notation, we always calculate O for the worst case scenario. That is, needing an item that is at the end of your loop. Say we add 1 to n. How many times it has to pass the loop now? 11 * 11 and that is 121. So whenever your input grows 1, the cost of this algorithm grows exponentially. That is why we say O(n^2).