I have following piece of code:int sum = 0;for (int i = 1; i <= N; i++)    for (int j = 1; j <= N; j++)        for (int k = 1; k <= N; k = k*2)            for (int h = 1; h <= k; h++)                sum++;So I'v calculated how much does each cycle executes and then whole script, and I think I might be wrong for the last one.1. N2. N3.  1 + log2N( means log N to the base 2)4. NSo the total execution amount of inner cycle would be N^3 * (1 + log2N).Am I right? How I can transform this statement?UPDATE 1I have another solution which seems monstrous:1. N2. N3. LOG2(N) + 14. 2^(LOG2(2N)) - 1So total cycles amount would be n^2 * (LOG2(N) + 1) * 2^(LOG2(2N)) - 1.Which transforms to n^2 order of growth.UPDATE 2I wrote simple test app to check my assumption.it seems that third cycle is already calculated for some reason is fourth one. At least this is the result of test app. I threw away (LOG2(N) + 1).As the result of several transformations I have following equation for total amount of sum++ calls:N*N*(2*N - 1) = 2 * N^3 - N^2 ~ N^3
How much times command executed? Looking for mistake
algorithms;algorithm analysis
The first two loops are not interesting - they just give N^2 multiplier.The fourth loop inside of third loop gives a geometrical progression: 1,2,4,8,...Totally it will increase sum by 2M-1 where M is the largest power of 2 less than N.So totally: N^2*(2*M-1)In terms of big-O that's O(N^3).