CODEWITHSUNDEEP
algorithmbig-otime-complexitynested-loops
Tehmas
Tehmas

Reputation: 83

Operation Count of this Loop

int sum = 0;

for (int i = 1; i < n; i *= 2) {
    for (int j = n; j > 0; j /= 2) {
        for (int k = j; k < n; k += 2) {
            sum += i + j * k;
            }
        }
    }

I am trying to calculate the operation count of the above given nested loop. The first and second loop variable is independent.

My try:

10n(logn)^2 + 1

How do I calculate it correctly? The most inner loop is the main problem.

Upvotes: 0

Views: 433

Answers (1)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

Methodically, you may proceed using Sigma notation:

enter image description here

enter image description here

enter image description here

Upvotes: 1

Related Questions