Q:

Time complexity while loop with recursion

   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);
       }
     }

For the time complexity of this loop. Is this thought process correct? In the main function, the loop is O(N). In the call function, the loop is O(N), which the recursion is n/2, therefore the O(logN)with base 2. So the overall time complexity of in the main is O(N)*[O(N)*O(LogN)]= O(N^2 Log N)?

A:

you can use recursion tree to figure out the number of calls and the order of recursion function is equal to the number of nodes in the recursion tree (leaves are call(n/2) that is not showing):

so to calculate the number of all nodes you can calculate summation and estimate the order (using geometric sequence by formula to calculate summation) :

Order of the main loop is less than , so main loop order is 

