1

In my code, both for loops have the same time complexity and same operation, however the second nested for loop takes almost 40 times more time than first one. Why is this happening?

I am using javac compiler and running my code in windows command prompt. 

import java.util.concurrent.TimeUnit;

class Elapsedtime
{
    public static void main(String[] args) throws InterruptedException 
    {
        int i,j,t,a;
        long startTime = System.nanoTime();
        for(i=0;i<1000000000;i++)
        {
            for(j=0;j<1000000000;j++)
            {
                a=j;
            }
        }
        long endTime = System.nanoTime();
        long timeElapsed = endTime - startTime;
        System.out.println("Execution time in nanoseconds  : " + timeElapsed + " ns.");
        System.out.println("Execution time in milliseconds : " + timeElapsed / 1000000 + " ms.");

        startTime = System.nanoTime();
        for(t=0;t<1;t++)
        {
            for(i=0;i<1000000000;i++)
            {
                for(j=0;j<1000000000;j++)
                {
                    a=j;
                }
            }
        }

        endTime = System.nanoTime();
        timeElapsed = endTime - startTime;
        System.out.println("Execution time in nanoseconds  : " + timeElapsed + " ns.");
        System.out.println("Execution time in milliseconds : " + timeElapsed / 1000000 + " ms.");
    }
}

I am getting the following output.

Execution time in nanoseconds : 17963700 ns. Execution time in milliseconds : 17 ms. Execution time in nanoseconds : 549485500 ns. Execution time in milliseconds : 549 ms.

but I don't expect much difference.

user11862325
  • 73
  • 1
  • 1
  • 7
  • Please move `long startTime = System.nanoTime();` to after initialization of variables `i, j`. (Just before for-loop). Variable initialization takes some CPU cycles too and update the timing – Sagar Chilukuri Jul 31 '19 at 07:36
  • 2
    This is not about loop execution but about how to write correct benchmarks in Java. This answer might help you understand: https://stackoverflow.com/a/513259/4949750 – Amongalen Jul 31 '19 at 07:37
  • 2
    @SagarCh 4 int slots should not take that much time if any at all. – Hans-Martin Mosner Jul 31 '19 at 07:39
  • @Hans-MartinMosner, Yeah, I understand. (In terms of benchmarking, it is still considered as warmup phase for 1st for loop, while for 2nd loop, there is no cost involved) – Sagar Chilukuri Jul 31 '19 at 07:42
  • There are small difference, In first code there are three loop and providing extra task over there to do that taking taking small extra time compare to below one. Example, in first after finishing the task `t=0` again it will check `t<1 when t=1` that also takes time and variable initialization also happening over there. – Null Pointer Jul 31 '19 at 07:44

1 Answers1

0

It is possible that during the first nested loop the optimizing compiler creates better code because it determines that there are going to be many iterations. The second loop will already run the optimized code.

You can test this by reversing the order of the two loops, still the first one will likely be slower.

Hans-Martin Mosner
  • 796
  • 6
  • 12