What is the time complexity of this? It uses 3 loops and the innermost loop depends on the outermost?

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).