Algorithm execution time?
There is a dynamic programming algorithm where you need to find the largest decreasing subsequence. The algorithm in this case is not important, I can not decide on the execution time of this main part of this search
int[] T = new int[7]; ///массив для поиска подпоследовательности
int n = T.Length; ///длина массива
for (int i = 2; i < n; i++)
{
for (int j = 1; j < i; j++)
{
// работаем с T за O(1)
}
}
If the second for ran from 1 to n, then it is clear that the execution time is n2 (n is the square), but in the above case, it turns out that? n log(n) ?
2 answers
See. The first inner loop has a length of 1, the second - 2, the third - 3, ..., the last - (n - 2).
The sum of the arithmetic progression is collapsed:
1 + 2 + ... + (n - 2) = (1 + (n - 2)) * (n - 2) / 2 = n^2/2 - 3n/2 + 1
If we need O - asymptotics, we get O(n^2).
The same is true on your fingers: from the square n × n , you only run through the upper (or lower, depending on how to index) triangle, that is, half of the square. The whole square O(n^2), its half too.
Here is read, extremely useful.
Introduction to Algorithm Complexity Analysis (Part 1)
Introduction to Algorithm Complexity Analysis (part 2)