Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the complexity of empty for loop?

Tags:

java

algorithm

I was wondering if the complexity of a empty for loop like below is still O(n^2)

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
    }
}

update : changed height and width variable to n

like image 204
mzz Avatar asked Jan 02 '23 16:01

mzz


1 Answers

If it won't get optimized out by the compiler, the complexity will still be O(n^2) (or actually O(N*M)) - even though the loops bodies are empty, the condition checks and incrementation of both counters are still valid operations which have to be performed.

like image 154
Szab Avatar answered Jan 05 '23 17:01

Szab