Timing Code Execution in Java

Here’s a method for calculating the nth Fibonacci number, written in Java.

	static int fibN(int n) {
		if(n <= 1) {
			return n;
		}
		else {
			return fibN(n-1) + fibN(n-2);
		}
	}

This method is great for demonstrating recursion but it's terribly inefficient for the task at hand. A more efficient method of computing the nth Fibonacci sequence would be to literally count from the first to the nth sequence number. To demonstrate this, I'll be timing the code execution of both the method above, fibN(), and the method below, fibN2().

	static int fibN2(int n) {
		int current 	= 1;
		int previous 	= 0;
		int next 	= 1;
		int temp 	= 0;

		for(int i = 1; i < n; i++ ) {

			temp = current;
			next = previous+current;
			current = next;
			previous = temp;
		}

		return next;
	}

I'll be using Java's System.nanoTime() to time this code. Each method will be called from within a loop 45 times, the nanoTime() being noted before the loop starts and when the loop ends in order to calculate execution time. Remember, end time minus start time equals duration. So, here's the full class for this process:

class Fib {
	
	static long startTime 	= 0;
	static long endTime 	= 0;
	static long duration	= 0;
	static long duration2	= 0;

	public static void main(String[] args) {
		System.out.println("Recursive: ");

		startTime = System.nanoTime();
		for(int i=1; i <= 45; i++)
			System.out.println(fibN(i));

		endTime = System.nanoTime();
		duration = (endTime - startTime);

		System.out.println("execution took " + duration + " nanoseconds");

		System.out.println("Non-Recursive: ");

		startTime = System.nanoTime();
		for(int i=1; i <= 45; i++)
			System.out.println(fibN2(i));

		endTime = System.nanoTime();
		duration2 = (endTime - startTime);

		System.out.println("execution took " + duration2 + " nanoseconds");

		System.out.println(duration + " vs \n" + duration2);
	}

	static int fibN(int n) {
		if(n <= 1) {
			return n;
		}
		else {
			return fibN(n-1) + fibN(n-2);
		}
	}

	static int fibN2(int n) {
		int current 	= 1;
		int previous 	= 0;
		int next 	= 1;
		int temp 	= 0;

		for(int i = 1; i < n; i++ ) {

			temp = current;
			next = previous+current;
			current = next;
			previous = temp;
		}

		return next;
	}
}

timing

This image shows the result of this code. As you can see, fibN2() is considerably faster than fibN(), thus proving that it's much more efficient to count up to the nth Fib number than it is to use recursion to find the nth number.

A final note, nanoseconds are pretty rubbish to work with to be honest. At least, in this example. So change
System.nanoTime()
to
System.currentTimeMillis()

instead to time the processes in milliseconds. This will give a more friendly result.

Bookmark the permalink.

Comments are closed.