functional-programmingtime-complexity

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?


Solution

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