CODEWITHSUNDEEP
big-o
blue3636
blue3636

Reputation: 11

What are the Big-Oh values for the running times of these code fragments?

I was wondering if someone could help me with the Big-Oh running times of these code fragments and explain how you get each one...thank you!

a.) 

int x = 0;
    for (int i = 0; i < n; i += 4){
         for (int j = 0; j < i; j++){
              x += i*j;
         }
    }

b.) 

int counter = 0;
    for (int i = 1; i < n; i = i*3){
        for (int j = n*n; j >= 0; j--){
             counter++;
        }
    }

c.) 

int x = 0;
    int i = 1;
    while (i < n){
        int j = 0;
        while (j < 2*n){
             x++;
             j = j+n;
        }
        i = i*2;
   }

Upvotes: 1

Views: 41

Answers (1)

Ashwani
Ashwani

Reputation: 2052

I will tell you how to do it for first problem and then you can do same for all.

In first problem, you have two loops. In outer loop you are starting from 0 and going upto n with increment of 4 in each iteration. Means your outer loop will run n/4 times. Now, 

For 1st iteration of outer loop your inner loop will run 0 or 0*4 times.
For 2nd iteration of outer loop your inner loop will run 4 or 1*4 times.
For 3rd iteration of outer loop your inner loop will run 8 or 2*4 times.

In general,
For pth iteration of outer loop your inner loop will run (p-1)*4 times.

number of times your innermost loop ran = 0*4 + 1*4 + 2*4 .............+ ((n/4)-1)*4.
                                        = 4 * (1+2+3..........+ (n/4)-1)
                                        = 4 * ((n/4)-1) * (n/4) * 1/2
                                        = (n^2)/8 + n/2
                                        = O(n^2)

Upvotes: 1

Related Questions