0
   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)?

tyc72
  • 65
  • 7
  • Does this answer your question? [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) – MartenCatcher Jan 26 '20 at 06:06
  • i am just having trouble with the recurison of (n/2) i am not sure if O(Log N) is correct – tyc72 Jan 26 '20 at 06:08
  • Hi tyc72. Welcome on stackoverflow. can you provide more details to your question. I recommend you also to have a look here: https://stackoverflow.com/help/how-to-ask – and-bri Jan 26 '20 at 06:28
  • I want to find the big o estimate for this given code. My question is whether O(n^2 log N) is correct for this code – tyc72 Jan 26 '20 at 06:33

1 Answers1

2

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):

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

enter image description here

Order of the main loop is less than enter image description here, so main loop order is enter image description here

Mehrdad Dowlatabadi
  • 1,335
  • 2
  • 9
  • 11