Algorithmic code growth order

Question

I attend the course online and stick to the following question. What is the worst-case growth order of the next code fragment as a function of N?

int sum = 0; for (int i = 1; i <= N*N; i++) for (int j = 1; j <= i; j++) for (int k = 1; k <= j; k++) sum++; 

I thought it was of order N^4 , but it seems that this answer is incorrect. could you explain?

Answer 1

One start of the inner loop increases sum exactly j times.

One run of the middle loop causes the inner loop exactly i times with values ​​of j between 1 and i (inclusive). Thus, it increases sum exactly 1+2+3+...i times, which is i.(i+1)/2 according to the well-known formula of "triangular numbers".

The outer loop causes the middle loop exactly N^2 times (denote it as M ) with i values ​​between 1 and M (inclusive). Thus, it increases sum exactly 1+3+6+...M.(M+1)/2 times. Similarly, this is M.(M+1).(M+2)/6 , according to the not-so-well-known "tetrahedral number" formula ( http://en.wikipedia.org/wiki/Tetrahedral_number ).

In general, the final value of sum is N^2.(N^2+1).(N^2+2)/6 .

In asymptotic terms, the inner cycle is O(j) , the average O(i^2) (by summing) and the outer O(M^3) (by summing), i.e. O(N^6) .

Also see the Faulhaber formula, which shows that the sum n^k is O(N^(k+1)) ( http://en.wikipedia.org/wiki/Faulhaber%27s_formula ).

Answer 2

It has order O(N^6) . You should notice that it is not true that each cycle simply adds order N to complexity. Consider the following example:

 int sum = 0; for (int i = 1; i <= M; i++) for (int j = 1; j <= i; j++) for (int k = 1; k <= j; k++) sum++; 

You should be able to easily determine the order of O(M^3) , so if you replace M=N^2 , then you will get an answer. The key point is that each inner cycle is of order O(N^2) in this case, but not O(N) .

Answer 3

Denote n = N^2 . Then the loop will be executed every time k <= i <= j . This will be approximately n^3/6 times. So the runtime is O(n^3)= O(N^6)

---

Explanation: Ignoring for a moment the cases when k==i or j==i or j==k , we take 1 out of 6 different triples:

  (a1,a2,a3) (a1,a3,a2) (a2,a1,a3) (a2,a3,a1) (a3,a2,a1) (a3,a1,a2) 

In general, there are n^3 triples. Only one of the 6 triples obeys the order.

Answer 4

Any given mileage of the inner loop (k) has a time proportional to j, but we must make one of them for each of j = 1 - j = i, and the sum 1 + 2 + ... + i grows as i ^ 2 Therefore, for any given I we have O (i ^ 2) operating time, but, of course, we need to deal with i = 1 through i = N ^ 2. The amount i ^ 2 for i = 1 through N ^ 2 grows as N ^ 6 .