Analysis of Basic Recursive Functions

Question

I'm trying to understand the contrast between run-time for this function

public static String f(int N) {
 if (N == 0) return "";
 String s = f(N / 2);
 if (N % 2 == 0) return s + s;
 else return s + s + "x";
}

and this function

public static String f(int N) {
 if (N == 0) return "";
 if (N == 1) return "x";
 return f(N/2) + f(N - N/2);
}

where string concatenation takes time proportional to the size of the strings.

So far, I believe that the first function is called log(N) times for input N and the second 2log(N) times. Is that right? Beyond that, I'm not sure how to think about how many operations happen in each of those calls. I know that for the first function, in the base case there are 0 operations (no concatenation), then 1 operation (concatenation of two null strings with a string of length 1?), then 2 operations. In general I believe the string produced by a call with N is of length N? But I just don't know where to start thinking about how it all adds up.

For the second one likewise I'm a little lost. I just need a way to approach the analysis. Keep in mind I'm not great with symbols, so if you're going to show off with symbols, I'd appreciate an explanation that will help me follow the symbols as well.

Answer 1

Set them up as recurrences. First, note that both just return $N$ characters $x$. Call the time taken by the first function for $N$ $A(N)$ and similarly $B(N)$ for the second. For the first version, the function calls itself with $\lfloor N / 2 \rfloor$ (I'm taking your language to be Java or similar, dividing integers truncates), and then concatenates some strings. As noted, $f(N)$ is just $N$ times 'x'. Consider teh different cases, and what work is done in each of them:

$$A(N) = \begin{cases} 0 & N = 0 \\ A(\lfloor N / 2 \rfloor) + 2 \cdot N / 2 & N > 0 \wedge 2 \mid N \\ A(\lfloor N / 2 \rfloor) + 2 \cdot (N - 1) / 2 + 1 & \text{otherwise} \end{cases}$$

You see that both last cases simplify to just $A(\lfloor N / 2 \rfloor) + N$. Your recurrence is $A(N) = A(\lfloor N / 2 \rfloor) + N, A(0) = 0$

For the second one, you get $B(N) = B(\lfloor N / 2 \rfloor) + B(\lceil N / 2\rceil) + N, B(0) = B(1) = 0$

• Simon: Given an initial $N$ that is a power of 2, say 2ドル^k,ドル we can solve your nice linear recurrence relations to obtain a closed form expression for $A$ or $B$ as a function of $k$. Please could you elaborate on how to extend that result to arbitrary values of $N$ ? Or at least, on how to extend the corresponding asymptotic formulae ?
• vonbrand: @Simon, exact formulas are possible, but quite messy...