function fun(N) {
let k = 0;
for(let i = N; i >= 1; i = i/2) {
for (let g = 1; g <= N/i;g = g + 1) {
for (let h =1; h <= i;h = h + 1) {
k = k + 1;
}
}
}
return k;
}
My analysis of the given problem is as follows:
The outer loop runs until i
becomes less than 1, and in each iteration, i
is divided by 2. This implies that the outer loop will run logarithmically in base 2 with respect to N
. Specifically, the outer loop will run until i
becomes less than 1, and the number of iterations can be expressed as log₂(N)
.
The middle loop runs for N/i
times, where i
is the control variable of the outer loop. Therefore, the middle loop contributes a factor of N
to the time complexity.
The innermost loop runs i
times, and is dependent on the outer loop. Thus we do not consider its time complexity.
Therefore, overall time complexity of the function is O(N log N)
, is it right?
Your answer of a time complexity of O(N log N)
is correct, but your derivation is not.
Consider the inner two loops involving g
and h
. The innermost loop with index h
runs i
times, thus having complexity O(i)
. The loop with index j
runs N/i
times, thus having complexit O(N/i)
. As these two loops are nested, the total complexity is O(i) * O(N/i) = O(N)
. Therefore, the time complexity of the inner two loops is independent of i
and is always O(N)
.
The outermost loop with index i
runs O(log N)
times, and your logic behind this is correct.
Thus, the total time complexity of all three loops is O(log N) * O(N)
, giving an answer of O(N log N)
.