Runtime Complexity 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.

General tip for determining time complexity - count the number of times each block of code containing only basic operations is executed, not the actual basic operations themselves. — meowgoesthedog
– meowgoesthedog, Commented Jun 11, 2019 at 8:49

plum 0 · Accepted Answer · 2019-06-27 20:47:36Z

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.

Collectives™ on Stack Overflow

Runtime Complexity of Basic Recursive Functions

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related