algorithm with $f(n) = log^2(n)$ 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 &gt;1
\end{cases}
$$
I have tried this way:

//the array starts from 1
    mergesort(A[], b, e)
    {
       if(b &lt; e)
       {
          p = (b+e)/2;
          mergesort(A, b, p);
          mergesort(A, p+1, e);
          for(i = 1; i &lt;= e; i = i*2)
             for(j = 1; j &lt;= 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 &lt; e)
               {
                  p = (b+e)/2;
                  mergesort(A, b, p);
                  mergesort(A, p+1, e);
                  for(i = 1; i &lt;= e-b; i = i*2)
                     for(j = 1; j &lt;= e-b; j = j*2)
                        puts("");
               }
            }
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&lt;x; i=i*2)
      for(j=1; j&lt;x; j=j*2)
         no-op;