CODEWITHSUNDEEP
javajava-streamtime-complexity
wannaBeDev
wannaBeDev

Reputation: 739

Time complexity in nested loops and streams

I would like the following assumption to be confirmed. The time complexity following nested for loops is identical:

List<Integer> smallList = List.of(1, 2, 3, 4, 5);
List<Integer> bigList = IntStream.range(1, 1_000_000).boxed().collect(Collectors.toList());

for (int i : smallList) {
    for (int j : bigList) {
        doSomething(i, j);
    }
}

for (int j : bigList) {
    for (int i : smallList) {
        doSomething(i, j);
    }
}

My assumption is that the time complexity is identical because 5 x 1_000_000 calls of doSomething is the same as 1_000_000 x 5 calls of doSomething. Is this right? If yes, is that also true if streams are involved?

smallList.stream().forEach(i -> bigList.stream().forEach(j -> doSomething(i,j)));
bigList.stream().forEach(j -> smallList.stream().forEach(i -> doSomething(i,j)));

Is the time complexity of both above statements identical?

Upvotes: 1

Views: 732

Answers (1)

Avi
Avi

Reputation: 2641

With regards to time complexity, yes - these operations operate identically in terms of "doSomethings" executed. 5 times 1 million is naturally equal to 1 million times 5.

The problem lies in the details - I would certainly not guarantee that these operations perform identically in the real-world, because you would run into real-world restrictions like memory usage, # of cores, caching/memory alignment issues, etc. Of course, if these issues don't heavily impact your performance in some unexpected way, then you would expect to see both operations take an approximately equivalent time to execute.

Upvotes: 1

Related Questions