Каков худший случай анализа этого фрагмента кода?

Question

sum = 0;
for (int i = 0; i < N; i++)
  for(int j = 0; j < i*i; j++)
    sum++;

Я не совсем уверен в своем ответе; Я думаю, что внутренний цикл выполняет операции i ^ 2, а внешний цикл выполняется N раз, поэтому окончательный ответ будет O (N ^ 3)?

Answer 1

Количество операций sum = 1 + 4 + 9 + ... + N^2. Это потому, что когда i = 0, j будет увеличивать себя 0 раз. Когда i = 1, j будет увеличиваться один раз. Когда i = 2, j будет увеличиваться 4 раз и т. Д.

Эта сумма равна N(N + 1)(2N + 1)/6, поэтому алгоритм действительно O(N^3). Вы можете доказать эту формулу по индукции.

Answer 2

Мне это кажется правильным (асимптотически).