Frequency Count Of Algorithms

I need to know how to determine the fr开发者_StackOverflowequency count of the sum:= sum+1 statement in the following program:

sum:=0

for i:=1 to n do
  for j:=1 to i do
    for k:=1 to j do
        sum:= sum+1
    end<br/>
  end
end

I would also like to know how, in general, to determine the frequency count of all algorithms not just this one specifically.

---

∑∑∑ 1 = ∑∑ j = ∑ (i*(i+1))/2 = ∑(i^2+i)/2 = (n(n+1)(2n+1)/6+n(n+1)/2)/2 = n(n+1)(n+2)/6

Your formula is this:

F(n) = n(n+1)(n+2)/6

And currently there is no general way for calculating running times, If there was some way, Complexity theory should be removed from Computer Science.

---

For the expression representing the exact frequency, you'll want to consult summation formulas for polynomials.

Namely, the inner loops are dependent on the current iteration of the outer loops. For instance:

sum := 0
for i:=1 to n do
  for j:=1 to i do
    sum := sum + 1

With respect to n, the sum is 1+2+3+4+5+...+n. In summation notation, it is Σ _i=1ⁿ i .

---

Alright, let's build this up from the inside out.

The line of code is executed j times each time the inner loop is run. So far so good.

So for each time the middle loop is run, we execute the statement 1 + 2 + 3 + ... + i - 1 + i times. Anyone should recognize that as equal to i * (i + 1) / 2. Or (i^2 + i) / 2

For each time we run the outer loop, we execute the statement ((1^2+1) + (2^2+2) + ... (n^2+n))/2 times.

I'll leave the final result as an exercise for the reader.

Though this problem is undecidable in general - if you knew how many times each line of code in a program would execute, you would have solved the Halting Problem.