Сложность двух чешуйчатых петель

Question

У меня есть этот алгоритм (в c кода для удобства):

int algo(int *T, int size) 
{ 
    int n = 0; 

    for (int i = 1; i < size; i++) { 
     for (int j = i; j < size; j++) { 
      n += (T[i] * T[j]); 
     } 
    } 

    return n; 
} 

Что такое время сложность этого алгоритма?

Моя ставка это n * log (n), так как мы имеем два внахлест итераций на size длины один раз, и на size - i во второй раз, но я не уверен.

Формальное доказательство сложности приветствуется!

Answer 1

Это алгоритм O (N).

• первой итерации внешнего цикла работает N-1 раз
• второй итерации внешнего цикла работает Н-2 раза
• третьей итерации внешнего цикла работает Н-3 раза
• .. .
• последней итерации внешнего цикла выполняется 1 раз

общее количество раз (N) + (N-1) + (N-2) + ... 1, который является sum of arithmetic progression. Формула для вычисления суммы равна N * (N-1)/2, которая равна O (N).