Algorithm Frequency

Question

I need to know how to determine the frequency of the totalizer counter: = sum + 1 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 the general case, to determine the frequency of all algorithms, and not just this particular one.

Answer 1

ΣΣΣ 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 as follows:

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

And there is currently no general way to calculate the lead time. If there was any way, the theory of complexity should be removed from Computer Science.

Answer 2

For an expression representing the exact frequency, you need to refer to the summation formulas for the polynomials .

, . :

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

n 1 + 2 + 3 + 4 + 5 +... + n. & ​​Sigma; _{= 1} ⁿ i.

Answer 3

, .

j , . .

, , , 1 + 2 + 3 + ... + i - 1 + i . , i * (i + 1) / 2. (i^2 + i) / 2

, , ((1^2+1) + (2^2+2) + ... (n^2+n))/2 times.

.

Although this problem is unsolvable in general - if you knew how many times each line of code in the program was executed, you would solve the problem with stopping.