algorithm with $f(n) = log^2(n)$
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;