Time Complexity of Nested For Loop with If

Question

void f(int n)
{
  for(int i =1; i<=n; i++){
    if(i % (int)sqrt(n)==0){
      for(int k=0; k< pow(i,3); k++){
        //do something
      }
    }
  }
}

My thinking process: number of times execute if statement: sum i=1 to n (theta(1)).

number of times execute things inside if: sum i=1 to sqrt(n) (for loop)

number of times execute for loops: sum k=0 to i^3 (theta(1)) = i^3

This will give me: theta(n) + sum i=0 to sqrt(n) (theta(i^3)) = theta(n) + theta(n^2)

which gives me theta(n^2)

The answer key he gave is theta(n^3.5)

I am just wondering if i made any mistake on my thinking process. I have asked my professor twice about this question. Just want to see if there is anything I didn't see before I bother him again.. Thanks!

Community · Accepted Answer · 2017-04-13 12:19:15Z

1

Using Sigma notation, I came up with the exact closed-form.

Besides, the formula below assumes the process, which doesn't verify the condition that executes the innermost loop, is negligible.

It's up to you to determine tight order of growth bounds, because of flooring function and square root etc.

Further details here: https://math.stackexchange.com/questions/1840414/summation-with-floor-and-square-root-functions-tight-bounds

edited Apr 13, 2017 at 12:19

CommunityBot

11 silver badge

answered Jun 25, 2016 at 5:11

Mohamed Ennahdi El Idrissi

2,9872 gold badges21 silver badges35 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Deepak Kumar · Accepted Answer · 2016-06-24 06:42:19Z

0

void f(int n) {   
  for(int i =1; i<=n; i++){     //---   n times
    if(i % (int)sqrt(n)==0){    // ---  2 times (constant)
      for(int k=0; k< pow(i,3); k++){  // sqrt(n)^3 and n^3 times
        //do something
      }
    }   
  } 
}

Taking the highest order term it should be Theta(n^3)

Assuming do something is constant

c = do somrthing + plus running cost of single iteration of inner loop

a = runnning cost of running single iteration of outer most loop

b = running cost of if block Thinking more about it cn^3/2 + cn^3 + a*n + b*2)

Taking the highest order term Theta(n^3) or since c is same coefficient for both the n^3 and n^3/2 we can reduce it

= cn^3 + cn^3/2

= cn^3(n^1/2+1)

~ cn^3 * n^1/2

= cn^3.5

edited Jun 24, 2016 at 6:42

answered Jun 23, 2016 at 5:54

Deepak Kumar

1512 silver badges6 bronze badges

Collectives™ on Stack Overflow

Time Complexity of Nested For Loop with If

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related