0
$\begingroup$

I have to write an algorithm that exactly reflects this recurrence: $$ T(n)=\begin{cases} Θ(1)\;\;\;\;n \leq 1\\ 2T(n/2)+log^2(n)\;\;\;\;n >1 \end{cases} $$ I have tried this way:

//the array starts from 1
    mergesort(A[], b, e)
    {
       if(b < e)
       {
          p = (b+e)/2;
          mergesort(A, b, p);
          mergesort(A, p+1, e);
          for(i = 1; i <= e; i = i*2)
             for(j = 1; j <= e; j = j*2)
                puts("");
       }
    }

does the algorithm respect the recurrence?

EDIT:

could a solution be?

//I have only changed the two fors
            mergesort(A[], b, e)
            {
               if(b < e)
               {
                  p = (b+e)/2;
                  mergesort(A, b, p);
                  mergesort(A, p+1, e);
                  for(i = 1; i <= e-b; i = i*2)
                     for(j = 1; j <= e-b; j = j*2)
                        puts("");
               }
            }
$\endgroup$
0
0
$\begingroup$

Your first algorithm as written cannot be correct since it has a time complexity of at least $\Omega(n \log^2 n)$ and the solution to your recurrence equation is $T(n)=\Theta(n)$. To see this notice that at least half of the $\Theta(n)$ leaves of the recursion tree requires time $\Theta(\log^2 n)$ to execute the two nested for loops at the end.

Your second algorithm is correct but it is overcomplicated and has a misleading name.

Assuming that $n$ denotes the value of the input (and not its size), that arithmetic operations require constant time, and that / denotes integer division, a simple algorithm is:

Input: a positive integer n.

f(n):
   if(n==0)
      return;

   f(n/2);
   f(n/2);

   for(i=1; i<x; i=i*2)
      for(j=1; j<x; j=j*2)
         no-op;
$\endgroup$
2
  • $\begingroup$ Excuse me, I didn't explain myself well. I need the algorithm to exactly reflect the recurrence, and not just the "final" complexity. Anyway, a solution could be: ``` for(i = 1; i <= e-b+1; i = i*2) for(j = 1; j <= e-b+1; j = j*2) puts(""); ``` ? $\endgroup$
    – Shyvert
    Apr 26 '20 at 20:58
  • $\begingroup$ Please edit your question to specify that, then. I'll edit the answer. Just the two for loops won't do that either because you'd be missing the recursive calls. $\endgroup$
    – Steven
    Apr 26 '20 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.