Give a tight big-oh run-time analysis for this code fragment

Question

public static long F (int N) {
    if ( N == 1 ) return 1;

    return F(N - F(N-1));
}

Now I thought the inside F(N-1) will execute N times for each of the F( N - F(N-1)) and so it will be N² but that doesn't seem to be the answer.

Can someone tell me why?

Answer 1

To figure this one out, let's imagine rewriting this code in an equivalent way:

public static int F (int N) {
    if ( N == 1 ) return 1;
    int k = F(N - 1);
    return F(N - k);
}

All I've done here is pull out the inner call to F(N - 1) and move it to the top-level so that we can more clearly see that this code makes two calls to F and that the second call is to a subproblem that depends on the first call.

To determine the runtime here, we'll need to figure out what k is so we can see what kind of recursive call we're making. Interesting, it turns out that F(N) = 1 for all N. You can spot this pattern here:

• F(1) = 1.
• F(2) = F(2 - F(1)) = F(2 - 1) = F(1) = 1
• F(3) = F(3 - F(2)) = F(3 - 1) = F(2) = 1
• F(4) = F(4 - F(3)) = F(4 - 1) = F(3) = 1

It's a great exercise to prove this by induction.

So this means that the call to F(N - k) will call F(N - 1). This means that the code is functionally equivalent to

public static int F (int N) {
    if ( N == 1 ) return 1;
    int k = F(N - 1);
    return F(N - 1);
}

This has recurrence relation

• F(1) = 1
• F(n) = 2F(n-1) + 1

Which solves F(n) = 2ⁿ - 1. (Again, you can formally prove this by induction if you'd like). Therefore, the complexity is Θ(2ⁿ).

To validate this, here's a (really hacky) C script that calls the function on a number of different inputs, reporting the returned value and the number of calls made:

#include <stdio.h>

/* Slightly modified version of F that tracks the number of calls made          
 * using the second out parameter.                                              
 */
static int F (int N, int* numCalls) {
  /* Track the number of calls. */
  (*numCalls)++;

  if ( N == 1 ) return 1;
  return F (N - F (N-1, numCalls), numCalls);
}

int main() {
  for (int i = 1; i < 10; i++) {
    int numCalls = 0;
    int result = F(i, &numCalls);
    printf("F(%d) = %d, making %d calls.\n", i, result, numCalls);
  }
}

The output is

F(1) = 1, making 1 calls.
F(2) = 1, making 3 calls.
F(3) = 1, making 7 calls.
F(4) = 1, making 15 calls.
F(5) = 1, making 31 calls.
F(6) = 1, making 63 calls.
F(7) = 1, making 127 calls.
F(8) = 1, making 255 calls.
F(9) = 1, making 511 calls.

Notice that evaluating F(i) always takes 2ⁱ - 1 calls (just as the theory predicted!) and always returns 1, empirically validating the mathematical analysis.