CODEWITHSUNDEEP
javaperformanceloopstime-complexity
Ravi Yenugu
Ravi Yenugu

Reputation: 3898

Difference in Time complexity of Loops

The reason for posting this question comes from here

Is there any Time complexity difference between the following Snippets of Code?

Code Snippet A:

public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            for (int j = 1; j < 2; j++) {
                if (i < 100)
                    System.out.println("Hi");    
            }    
        }    
    }

Code Snippet B:

public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {    
            if (i < 100)
                System.out.println("Hi");    
        }    
    }

The Difference in code between the two is that Snippet B doesn't contain the inner loop from Snippet A which doesn't serve any purpose hence removed.

My assumptions:

Both Snippet A: and Snippet B: takes O(n) for large values of n

There could be some differences in space complexity since we have another loop variable j in Snippet A

Observation:

I tested the similar version of this loop structure in VBA and the Snippet B is a little faster than Snippet A

Is it because of space or time complexity differences or both?

Upvotes: 1

Views: 436

Answers (2)

Joel
Joel

Reputation: 4762

TECHNICALLY, both of your examples run in constant time.

If you were to switch your first for loop to count up to N or some variable, then they would both run in O(N). There is no difference in time complexity since then they would both be O(N) plus a constant time operation, resulting in just O(N).

The reason code snippet A is slower is because there is still a loop overhead (incrementing and comparing j).

Upvotes: 3

Kah
Kah

Reputation: 647

The overhead from intializing, comparing, and incrementing j would slow A, but I don't see a practical application for the inner loop.
This would definitely be shot down in production code since it reduces readability.

Upvotes: 1

Related Questions