-3

Time complexity of nested for-loop goes into the mathematical derivation through summation of two loops O(n2) complexity.

I tried an exercise to derive how i can get O(n3) for the following examples of three nested loops.

Simple three nested loops.

   for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
                 print(i * k * j);

Summation is = (n + n + n + .... + n) + (n + n + n + ... + n) + ... + (n + n + n + ... + n)

= n^2 + n^2 + .... + n^2

n times n^2 = O(n^3)

Three nested loops not run n times from beginning

 for(int i = 1; i <= n; i++)
     for(int j = i; j <= n; j++)
         for(int k = j; k <= n; k++)
             print(i *j * k)

The above is a pretty common form of nested loops and i believe the summation would be something as follows

= (n + (n -1) + (n -2) + (n - 3) + ... + 1) + ((n -1) + (n - 2) + (n - 3) +... + 1) + ((n -2) + (n -3) + (n - 4) + ... + 1) + ... + ((n - (n -2)) + 1)

= n(n - 1) /2 + (n-1) (n -2) / 2 + (n-2)(n-3)/2 + .... + 1

= From here i am slightly not sure if my logic is correct . I believe each of the above evaluate to a polynomial whose greatest value is n2 and as thats what we care about in time complexity, the above equation breaks down to.

= n^2 + n^2 + n^2 +... +n^2

= which is n times n^2 = O(n^3).

Is my assumption correct?

Three nested loops not run n times from end

for(int i = 1; i <= n; i++)
     for(int j = 1; j <= i; j++)
         for(int k = 1; k <= j; k++)
             print(i *j * k)

If the above was a two nested loop the summation would have been 1 + 2 + 3 + 4 + ... + n. However, for the three nested occurence i am deducing it to be

= 1 + (1 + 2) + (1 + 2 + 3) + (1 + 2 + 3) + (1 + 2 + 3 + .... + n)

From here i am not sure how to derive O(n^3) or how the above summation would be further simplified.

Community
  • 1
  • 1
Saad
  • 915
  • 9
  • 19
  • The summation of the first loop is `n*n*n` which is `O(n^3)`, and so is the second. You aren't doing yourself any favours by omitting the exponentiation operator. – user207421 Jul 29 '16 at 02:12
  • The loops should be in the form (x = 0; x < n; x++) to get n loops. I'm guessing that you're also considering combinations: for(i = 0; i < n-2; i++){ for(j = i+1; j < n-1; j++){ for(k = j+1; k < n; k++){ ... }}}, which is the number of combinations of n things taken 3 at a time. – rcgldr Jul 29 '16 at 02:18
  • Try to estimate how many times the inner loops run on the average. – n. m. could be an AI Jul 29 '16 at 02:19
  • The people who downvoted this, would please care to explain? – Saad Jul 29 '16 at 02:35
  • 2
    I'm voting to close this question as off-topic because this is maths and not programming. – Paul Hankin Jul 29 '16 at 02:58
  • 1
    @Saad The existing comments are sufficient to explain downvotes. There is no such thing as *O(n3)*. There is however such a thing as *O(n^3).* Do you ever plan to correct your post? – user207421 Jul 29 '16 at 03:00
  • @PaulHankin It is rather basic algorithmic complexity theory, and there are many questions about it here. – user207421 Jul 29 '16 at 03:01
  • I corrected it right away as you can see in the post. – Saad Jul 29 '16 at 03:02
  • 1
    You've fixed a few occurrences. Not all. Question remains unclear. – user207421 Jul 29 '16 at 03:03
  • oops..................... – Saad Jul 29 '16 at 03:03

1 Answers1

1

Using the fact that: 1+2+3+...+i =i*(i+1)/2, the summation above can be written as: 1*(1+1)/2 + 2*(2+1)/2 + ... + n*(n+1)/2. Obviously i*(i+1) > i^2, therefore:

1*(1+1)/2 + 2*(2+1)/2 + ... + n*(n+1)/2 > (1^2+...+ n^2)/2, as we know:

1^2+...+n^2 = n^3/3 + n^2/2 + n/6 (can prove this by induction).

Therefore, the original sum S is bigger than:

n^3/6 + n^2/4 + n/12, which is O(n^3).

Yerken
  • 1,944
  • 1
  • 14
  • 18
  • 1
    In case anyone is curious, the exact formula is n^3/6 + n^2/2 + n/3. One way to determine this is to do a polynomial curve fit. – rcgldr Jul 29 '16 at 02:52
  • The easy way: https://www.wolframalpha.com/input/?i=sum(sum(sum(1,+for+k+%3D+1+to+j),+for+j%3D1+to+i),+for+i+%3D+1+to+n) – Paul Hankin Jul 29 '16 at 05:23