CODEWITHSUNDEEP
recurrence
Alex Leibowitz
Alex Leibowitz

Reputation: 1605

Runtime Complexity of Basic Recursive Functions

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.

Upvotes: 0

Views: 51

Answers (1)

plum 0
plum 0

Reputation: 721

For a way to approach your analysis, I recommend simplifying your recurrence. You have F(n/2) + F(n-n/2). The second half of that can be simplified (F(n-n/2) = F(2n/2 - n/2) = F(n/2)). This means you are essentially calling f(n/2) two times for every iteration, which is indeed 2log(n). You have strictly constant time operations in both of those examples (i think) outside of the recurrence.

As far as I can tell, both of these should produce a similar output, with the exception that in the first example you will be tacking on an "x" for every n that is odd. This should lead to an extra n/2 x's multiplied by the log(n) number of x's? I'm not entirely certain if that is correct. I also believe that your first example runs in 2log(n) time, since you are calling f(n/2) twice until n is 0.

Note: I'm not the greatest at this but I gave it my best shot.

Upvotes: 1

Related Questions