3
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?

5
  • 7
    No you are wrong. Outer loop is O(n), inner one is O(n), and the inner most one is O(n). In total you have O(n^3).
    – perreal
    Aug 29, 2014 at 8:24
  • 2
    This question appears to be off-topic because it is about asymptotic analysis.
    – tmyklebu
    Aug 29, 2014 at 8:25
  • 2
    @Juan, j starts at 4 but goes up to n - 1.
    – perreal
    Aug 29, 2014 at 8:27
  • 1
    @tmyklebu: Not off topic for SO Aug 29, 2014 at 8:39
  • @MichaelFoukarakis: Sure it is. It has nothing to do with programming; the CS stackexchange is the right place for this question if anything is. (Aside from that, this question is almost certainly a duplicate many times over.)
    – tmyklebu
    Aug 29, 2014 at 8:50

3 Answers 3

2

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).

2

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!

2
  • i see. what about the middle loop? its not summation? Aug 29, 2014 at 15:07
  • I am seeing three loops, as I am seering three summations. I am not sure what your question is about. Aug 29, 2014 at 16:38
1

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).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.