[اللمار]

هذا المثال يمكن يساعد

Example 2



for (i = 0; i < n; i++)
for (j = 0; j < i; j++)
A[i][j] = 0;


Analysis: This code zeroes out the lower triangular part of a two-dimensional array. Since the inner loop is executed a variable amount of times, we can't just multiply n by i:

When i = 0 the inner loop is executed 0 times.
When i = 1 the inner loop is executed 1 time.
When i = 2 the inner loop is executed 2 times.
So the number of times the statement "A[i][j] = 0" is executed is: 1 + 2 + 3 + ... + n
This sum comes up a lot in algorithm analysis. You should memorize the formula:

1 + 2 + 3 + ... + n = n(n+1)/2
يعني استخدم قانون summation of k^2

= 1/2(n2 + n)

Since in Big-Oh analysis we ignore leading constants (the 1/2 in the equation above) and lower order terms (the n in the equation above), this algorithm runs in O(n2) time

لكن لو اضفنا كمان loop داخلي كيف يكون الحل ؟؟