What is the complexity for the following piece of code, O(logn) or O(nlogn)?
int i=1;
while (i<= n) {
int j = i;
while (j > 0) {
j = j/2;
}
i++;
}
I asked chatgpt and sometimes it says O(logn) and sometimes O(nlogn). The argument for O(logn) is that the inner loop dominates the number of iterations and that it should be taken, and the argument for O(nlogn) (which I find more reasonable) is that this is the sum of logarithms from 1 to n, which is logn!, which can be approximated to O(nlogn). I also saw this stackoverflow question and one of the answers is O(nlogn) and the other O(logn).
It is O(n logn).
It is easy to disprove O(logn): The outer loop executes exactly n times, so the algorithm must be Ω(n). At this point it doesn't matter even if the inner loop would execute 0 times because it is still a constant-time operation.
Proving that it is indeed O(n logn) is a bit more tricky and involves some math, but that's not really what you are asking so I won't get into that. But in cases like this, you can perform a very easy sanity check, by just counting the number of iterations the inner loop will perform:
int i=1;
counter = 0;
while (i<= n) {
int j = i;
while (j > 0) {
j = j/2;
counter++;
}
i++;
}
The value of counter for different inputs of n will answer your question in practice, even if it's not a formal proof.
As for ChatGPT, it is important to remember that it's far from an authority, so I would disregard it and not think too much about how it might have picked up that argument about O(log n). If we must speculate, then I suppose ChatGPT might have learned that argument from other contexts, such as when you have two parallel (not nested) loops where one takes more time than the other. Then, the slower one will dominate and let you ignore the faster one. But obviously that argument is applied incorrectly here. So yes, your own logic seems fine to me.