CODEWITHSUNDEEP
algorithmtime-complexity
Manoj
Manoj

Reputation: 5867

How to calculate time complexity for below function?

What is the time complexity for the below function?

void function(int n){
        for(int i=0; i<n; i++){. //n times
            for(int j=i ; j< i*i; j++){ // n*n times
                if(j%i == 0){
                    for(int k=0; k<j; k++){ // j times = n * n times.
                        ++counter;
                    }
                }
            }
        }
    }

Book says O(n^5). But I couldn't understand why book didn't take j%i into account. The k loop determines based on that. Can you clarify?

Upvotes: 3

Views: 322

Answers (2)

pseudo_teetotaler
pseudo_teetotaler

Reputation: 1575

Let's consider the part of code in which u have doubt : 

for(int j=i ; j< i*i; j++)
{ 
  if(j%i == 0)
        {
               for(int p=0; p<j; p++){ 
               ++counter;
        }
      }

Let's just analyse this part of code . For every i, j%i==0 will be true whenever j is a multiple of i, i.e. 

 i, 2i, 3i, .... i*i // upto i*i only,since j<i*i

Now, for every j, Inside complexity is O(j).

So Complexity for this part of code is :

enter image description here

So, Overall Complexity = O(n*n^3) = O(n^4)

Upvotes: 1

Charles
Charles

Reputation: 11479

In fact the function runs in time O(n^4), since the if condition happens only once every approximately n loops. See below for precise analysis.

void function (int n) {
    for(int i=0; i<n; i++) {
        // Runs a total of n times
        for(int j=i; j< i*i; j++) {
            // Runs a total of (n^3 - n)/3 = O(n^3) times
            if(j%i == 0) {
                // Runs a total of (n^2 - n)/2 = O(n^2) times
                for(int k=0; k<j; k++) {
                    // Runs a total of (3n^4 - 10n^3 + 9n^2 - 2n)/24 = O(n^4) times
                    ++counter;
                }
            }
        }
    }
}

Upvotes: 1

Related Questions