So I want to figure out the runtime of the following algorithm (in pseudocode):

Algorithm(N):
    int i = n;
    int j;
    new Array sum[(n   1) / 2];
    while i > 1 do
        j = i;
        while j < n do
            for k = 0; k < n; k = k   2 do
                sum[k / 2] = sum[(k / 2) - 1]   k;
            end
            j = j * 2;
        end
        i = i / 2;
    end 
    return sum

CodePudding user response：

The outer loop will make _⌊log₂