# 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 >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("");
}
}


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;

• 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("");  ? Apr 26 '20 at 20:58
• 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. Apr 26 '20 at 21:01