Оценка Big O с l oop и рекурсией

Question

     void call(int n)
       {
         for (int j=1;j<=n;j++)
         {
           call(n/2);
          }
       }

     void main()
      {
        int i;
        for (i=1;i<=n;i++)
         {
           call(i);
         }
       }

Я хочу определить наилучшую оценку для этой функции. Мой подход - главная функция - O (N). Я думаю, что функция вызова O (N * LogN). будет общая сложность времени O (N ^ 2 Log N)?

Answer 1

Оценка Big O рассчитывается следующим образом:

вызов метод: ввод n там имеет значение al oop в функции, поэтому O (N) рекурсия оценивается следующим образом:

T(n/2) -- T(n/4) -- T(n/8) -- T(n/16) ... O(logn)

, поэтому метод вызова nlogn

main метод

1*call(1) -- 2call(2) -- 3call(3) -- ncall(n) since call(n) is O{nlogn) so n^2logn