Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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. N
2. N
3.  1 + log2N( means log N to the base 2)
4. N

So the total execution amount of inner cycle would be N^3 * (1 + log2N).

Am I right? How I can transform this statement?

UPDATE 1

I have another solution which seems monstrous:

1. N
2. N
3. LOG2(N) + 1
4. 2^(LOG2(2N)) - 1

So total cycles amount would be n^2 * (LOG2(N) + 1) * 2^(LOG2(2N)) - 1.

Which transforms to n^2 order of growth.

UPDATE 2

I 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
share|improve this question

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
So what would be your verdict? May I consider, that this would be N^3 or N^2? From your opinion I would think that this would be N^3. Because, in general I would need the worst case solution. And worst case is when M == N, another words M is power of 2. –  Jevgeni Smirnov Feb 13 '13 at 12:55
2  
It could make sense to make more clear that you want big-O estimation, not exact answer ;), yes, it will be O(N^3). –  maxim1000 Feb 13 '13 at 13:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.