У меня есть эта функция, которая мне нужна для анализа времени выполнения с помощью Big-Theta, чтобы обеспечить наихудшее время выполнения.Я новичок в этой теме и могу использовать некоторые рекомендации по следующей функции.
int C(int a[], int n) {
int x=0, i, j, k;
for(i=0; i<n; i++){
for(j=0; j<i; j++)
x += a[j];
for(k=1; k<n; k = k*2)
x += a[k];
}
Я понимаю, что первый цикл вводится O (n) раз, а третий цикл for выполняется O (logn) раз,Где у меня возникла проблема со вторым циклом for.Эта часть выполнена O (n) или O (n ^ 2) время и почему?Как бы я должным образом проанализировал это, чтобы получить наихудший случай с малым временем выполнения?