How would I find the time-complexity of a recursive method in Java?

Question

I haven't been able to grasp the concept of complexity fully and I was wondering how I would be able to calculate it for method f(n) in this code:

import java.util.Random;

public class Main {
  public static void main(String[] args) {
    Random r = new Random();
    r.setSeed(System.currentTimeMillis());
    int n = r.nextInt(20) + 1;
    f(n);
  }

  private static void f(int n){
    if(n > 0){
      g(n);
      System.out.println();
      f(n-1);
    }
  }

  private static void g(int n){
    if(n > 0){
      System.out.print('X');
      g(n-1);
    }
  }
}

I understand that this is a recursive method which is what is confusing me. I see that every time the function f() is called, g() is is called, and run n times, and then f() calls itself as n-1 again until n=0. I don't know where to start Any help would be great. thanks.

Answer 1

A common technique for determining the runtime of recursive functions is to write out recurrence relations that describe the runtime as a quantity defined in terms of itself. Let's start with g. If we let c_n denote the runtime of g(n), then we have

• c₀ = 1 (calling g(0) takes a constant amount of work)
• c_n+1 = c_n + 1 (calling g(n) does a constant amount of its own work, then calls g(n-1)

We can look over a couple of values to c to see if we spot a pattern:

• c₀ = 1
• c₁ = c₀ + 1 = 1 + 1 = 2
• c₂ = c₁ + 1 = 2 + 1 = 3
• c₃ = c₂ + 1 = 3 + 1 = 4

Generally speaking, it looks like c_n = n + 1. You can formalize this by using a proof by induction if you'd like, but for now we're going to take it on faith. This means that the runtime of g is O(n).

Now, let's let d_n be the runtime of calling f(n). Notice that

• d₀ = 1 (calling f(0) does a constant amount of work)
• d_n+1 = d_n + c_n+1 (calling f(n+1) calls g(n+1), requiring c_n+1 work, then calls f(n)

We can expand this out to see if we see a pattern.

• d₀ = 1
• d₁ = c₁ + d₀ = 2 + 1
• d₂ = c₂ + d₁ = 3 + 2 + 1
• d₃ = c₃ + d₂ = 4 + 3 + 2 + 1

Generally, it looks like d_n = n + (n-1) + (n-2) + ... + 1. You can formalize this by induction if you'd like. This is a famous sum, and it works out to n(n+1) / 2. This quantity happens to be Θ(n²), so the overall runtime is Θ(n²).