Большая временная сложность алгоритма

Question

Что такое большое время этого алгоритма? Входные данные: массивы A и B, каждый из которых сортирует n> = 1 целое число Вывод: количество элементов в B равно сумме префиксных сумм в A

c=0
for i=0 to n-1 {
  s=0
  for j=0 to n-1 {
    s=s+A[0]
    for k=1 to j {
      s=s+A[k]
    }
  }
  if B[i]=s {
    c=c+1
  }
}
return c

Я получил n (n + 2) (n + 2) +1, что равно n ^ 3 + 4n ^ 2 + 4n + 1, что равно O (n ^ 3)

Answer 1

Чтобы определить порядок роста, формально вы можете действовать следующим образом:

Answer 2

Если вы просто ищете здесь BigO, все, что вам нужно сделать, это выяснить количество циклов, сколько из них вложено. В вашем случае у вас есть два цикла (вложенных), следовательно, это будет O (n * n) = O (n ^ 2)

P.S Несмотря на то, что ваш внутренний цикл не повторяется столько раз, сколько внешний, BigO остается неизменным.