CODEWITHSUNDEEP
javarecursionbig-otime-complexity
user5470380
user5470380

Reputation: 91

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

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.

Upvotes: 7

Views: 5316

Answers (3)

Linus
Linus

Reputation: 894

While not a general strategy for analyzing recursion, your f(n) is essentially a loop running g(k) for values of k spanning 1 to n. So the run-time of f(n) is essentially the summation of run-times of g(n), g(n-1), ..., g(2), g(1).

Since you already know the run-time of g(k) is essentially k, your ultimate run-time is a summation from 1 to n. If you know your summation formulas you'll know its order is O(n2).

Upvotes: 2

Warren Dew
Warren Dew

Reputation: 8928

First, calculate the number of times g() is called as a function of the initial argument n passed to f(). This gives you the amount of time taken by the function, as a multiple of the time it takes g() to execute, exclusive of recursion.

Then drop coefficients and lower order terms. For example, if your result was 0.5n^2 + 0.5n, you would drop the 0.5n since it was a lower order term - not squared - leaving 0.5n^2, and you would drop the 0.5 coefficient, leaving n^2. This would mean the function runs in O(n^2) time.

Upvotes: 2

templatetypedef
templatetypedef

Reputation: 372814

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 cn denote the runtime of g(n), then we have

  • c0 = 1 (calling g(0) takes a constant amount of work)
  • cn+1 = cn + 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:

  • c0 = 1
  • c1 = c0 + 1 = 1 + 1 = 2
  • c2 = c1 + 1 = 2 + 1 = 3
  • c3 = c2 + 1 = 3 + 1 = 4

Generally speaking, it looks like cn = 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 dn be the runtime of calling f(n). Notice that

  • d0 = 1 (calling f(0) does a constant amount of work)
  • dn+1 = dn + cn+1 (calling f(n+1) calls g(n+1), requiring cn+1 work, then calls f(n)

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

  • d0 = 1
  • d1 = c1 + d0 = 2 + 1
  • d2 = c2 + d1 = 3 + 2 + 1
  • d3 = c3 + d2 = 4 + 3 + 2 + 1

Generally, it looks like dn = 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 Θ(n2), so the overall runtime is Θ(n2).

Upvotes: 6

Related Questions