Сложность 2 для петель внутри 1 для петли

Question

for(int i=1;i<=n*n;i++)
{
   for(int j=1;j<=i/2;j++)
   {
         s=s+i+j;
   }
    k=1;
   while(k<j)
   {
        s=s+k;
        k=k*2;
   }
}

Итак, я знаю, что сложность O (n ^ 4), но я не совсем понимаю, как туда добраться. Я знаю, что первый l oop имеет n * n , так что это больше. Однако 2 for внутри другого обычно означают O (n ^ 2), поэтому у меня просто (n ^ 2) ^ 2, из-за первого n * n ? Или два форса внутри означают n каждый? Второе значение for выполняется только для одинаковых значений i и третьего, возможно, это считается. Пожалуйста помоги. Я в замешательстве, потому что помню один пример того, что 2 fors внутри другого for это O (n ^ 2 * logn). Если кто-нибудь захочет объяснить это, я буду благодарен.

Answer 1

Так что ваше первое предположение в значительной степени верно. Внешнее значение для (i) будет go для n ^ 2 итераций. Внутренняя часть для (j) также будет стоить не более n ^ 2 в одной итерации. while в этом случае можно игнорировать (вы можете использовать n ^ 2 как очень грубую верхнюю границу для него). Итак, у вас есть n ^ 2 xn ^ 2, и это ваше n ^ 4.