8/31 A bit more on the analysis of bubble sort and Recursion

In the analysis of BubbleSort we used the fact that

	1 + 2 + .... + (n-1) = n(n-1)
			       ------.
				 2
In general, the sum of the first n natural numbers is
given by the following formula:

	1 + 2 + 3 + ... + n = n(n+1)
			      ------.
				2
An easy way to see this is the following. Let

	S = 1 + 2 + 3 +.... + (n-1) + n.	(1)

Reverse this summation and rewrite S as
	
	S = n + (n-1) + ....+ 3 + 2 + 1.	(2)

Add the two equations, making sure that the 1st term in (1)
and the 1st term in (2) are added, the 2nd term in (1) and the
2nd term in (2) are added, and so on. So we get

	2S = (n+1) + (n+1) + ... + (n+1).

Note that there are n terms in this summation. So

	S = n(n+1)
	    ------.
	      2

Replacing n by n-1 in the formula gives us the sum of the first
n-1 terms.

Arithmetic series

The sum 1+2+3+...+n is a special case of the more general arithmetic
series:

	a + (a+d) + (a+2d) + ... + (a +(n-1)d)

The above summation has n terms, its first term is a, and each subsequent
term is d more than the previous term. Using the formula for the sum of
the first n natural numbers, we can derive the formula

a + (a+d) + ... + (a + (n-1)d) = n*a + d*n(n-1)
				       -------.
					  2

For example, what is the sum

	1 + 6 + 11 + 16 + ...,

assuming that there are n terms in the summation? Here a = 1, d = 5 and
we plug these in the above formula to get

	n + 5n(n-1)/2 = 2.5 n^2 - 1.5 n.

Example: Consider the following code fragment

	for(i = 0; i < n; i = i + 10)
		for(j = 0; j < i; j++)
			stuff that takes O(1) time

Note that the inner loop executes i times. Since the running time of
the body of the inner loop is assumed to be O(1), for each i, the
running time of the inner loop is A*i + B, where A and B are constants
independent of i or n. So the total running time is

(A*0 + B) + (A*10 + B) + (A*20 + B) +...

Note that there are n/10 terms in this summation. This can be simplified to

B*n/10 + A*(0 + 10 + 20 +...).

Using the geometric series formula with a = 0, d = 10, and n/10 terms,
we can simplify the above expression to

B*n/10 + A*(5*n(n-10))/100 = O(n^2).
	
Recursion
We start with the standard example of recursion, computing the nth Fibonacci number.
The Fibonacci number sequence is

	1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...

In general, f(1) = 1, f(2) = 1, and f(n) = f(n-1) + f(n-2) for n greater than 2.
This definition can be implemented by the following recursive function.

	public static int fibo(int n)
	{
		if((n == 1) || (n == 2))
			return 1;
		else
			return fibo(n-1) + fibo(n-2);
	}