So here is the code:
while (n > 0) {
n /= 2;
}
for (let i = 0; i < n; i ++) {
// Do something
}
The time complexity of the while
loop is O(log base 2 n)
, while the for
loop is simply O(n)
. So, is it O(log2n)
, O(n)
or something else?
Both your assumptions about each individual loop are correct, but when put together you can't simply add them up for the total time complexity. Those are mostly determined by the most influential part of the code, and a O(n)
will completely dominate the total runtime , making the first O(log2 n)
loop negligible in the long run, so a first simplistic answer would be O(n)
.
However, consider that the operations made by the first loop influence the second one, in particular here by changing the n
variable that's the main scaling factor of the second loop.
By the time the first loop ends n
will be either 0 or negative (you would keep looping while it's positive), and that means that the loop condition i < n
will never be true if i
starts from zero, so the second loop will never execute a single time. Therefore its time complexity doesn't depends on anything, so it'll be O(1)
. And in this case, the complexity of the full code will be O(log2 n)
, as the runtime of the first loop will dominate the second.
In general, try to look at the full code rather than individual parts, as they often interacts with each other, and only do separate analysis when you can be sure that execution of one won't affect the execution of the other and the blocks are really independent.