CODEWITHSUNDEEP
javac++algorithmruntime
S. James
S. James

Reputation: 77

analysis of algorithm run time

What would the big-O run time be? I'm mostly confused about the while loop run time. I know the run times for both for loops are O(n).

cin >> n >> min >> max;

for(int i = min; i < n; i++) {

     for(int j = 1; j < max; j++) {

        total = 1;

        while(total < n) {

             total = total *2;

        }

    }
}

Upvotes: 3

Views: 105

Answers (2)

janos
janos

Reputation: 124648

First of all, it looks like you forgot to put braces. I'm your code, as it is, the whole loop is not inside the nested for loops. As it is, we have a pointless nested for loop that just sets total to 1, followed by an independent while loop. The complexity of the first is O((n - min) * max), and the second is O(log(n)). The total time complexity is the sum of these.

Probably what you really meant is this:

for(int i = min; i<n; i++) {

 for(int j =1; j< max; j++) {

    total = 1;

    while(total < n) {
         total = total *2;
    }
  }
}

Here, we have the whole loop inside the nested for loops. The time complexity is the multiple of what we calculated earlier, so O((n - min) * max * log(n)). If min and max are constants, then we can reduce to O(n log n)

Upvotes: 1

R Sahu
R Sahu

Reputation: 206567

The progression of target in the while loop is:

1 2 4 8 ... 2^P

You need log(2, n) steps -- i.e. log of n in base 2. That loop is O(log n).

Upvotes: 3

Related Questions