CODEWITHSUNDEEP
calgorithmdata-structuresbig-o
user3923936
user3923936

Reputation: 71

What is the worst-case time-complexity of this algorithm?

void intFunction (int n, int value)
{
     int b,c;
     for (int j = 4; j < n; j++) {
          for (int i = 0; i < j; i++) {
               b *= val;
               for (int k = 0; k < n; ++k)
                    c += b;
          }
     }
}

I just learned the Big-O notion. so for this code, from my understand, the outside loop run time is n, and second inner one runs n(n+1)/2, and inner one is n(n+1)/2 as well. so the running time would be O(N^5)? am I right?

Upvotes: 3

Views: 179

Answers (3)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

Solving the following formula would give you the exact number of iterations (and deduce the order of growth complexity):

enter image description here

Result empirically verified!

Upvotes: 2

Am_I_Helpful
Am_I_Helpful

Reputation: 19168

Let's go with the number of iterations TO get verified about time-complexity!

First loop--->

for (int j = 4; j < n; j++){...}  // it will iterate for n-4 times.

Second loop--->

for (int i = 0; i < j; i++){...}  //it'll iterate for j-1 times for each iteration of outer loop started by j. See,this is dependent on First Loop(the outermost loop)...

Third Loop--->

for (int k = 0; k < n; ++k){...}  //it'll always run n times independent to any previous-iteration whenever it is executed

So, the overall iteration for the cases will be(in a much simplified version) :-

(n-4)*(j-1)*n times.

But,j itself varies from 4 to n-1. So, j is kinda dependent on n. i.e.,4<=j<=n-1. //so, here j will iterate n-5 times...

The exact treatment will be kinda this :-

n*n-5*n=n^3-5*n^2.

It is equal to O(n^3).

So, going in the worst case analysis, the number of iterations will be n^3-5*n^2 and it's time complexity will be O(n^3).

Upvotes: 1

perreal
perreal

Reputation: 98088

The outer loop:

for (int j = 4; j < n; j++)

iterates n - 4 times, so it is O(n). The inner loop:

for (int i = 0; i < j; i++)

iterates at most n - 5 times, so this is also O(n). The inner most one:

for (int k = 0; k < n; ++k)

iterates n times so it is O(n). The final complexity is O(n * n * n) = O(n^3).

Upvotes: 2

Related Questions