• Substitution Method, guess a bound and then use mathematical induction to prove our guess correct
• Recursion-Tree Method, converts the recurrence into a tree whose nodes represent the costs incurred at various levels of the recursion
• Master Method

• Brute-force, O(n²)

import javafx.util.*;

public class S
{
	public static Pair<Integer, Integer>maxArray(int [] array)
	{
		int max = Integer.MIN_VALUE;
		int m = 0, n = 1;

		for(int i = 0; i < array.length-1; i++)
			for(int j = i+1; j < array.length; j++)
			{
				if(array[j] - array[i] > max)
				{
					max = array[j] - array[i];
					m = i;
					n = j;
					System.out.println(m+" "+n);
				}
			}
		return (new Pair<Integer, Integer>(m, n));
	}

	public static void main(String args[])
	{
		int [] prices = {100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97};

		Pair<Integer, Integer> p = maxArray(prices);

		System.out.printf("%d to %d, sum is %d\n", p.getKey(), p.getValue(), (prices[p.getValue()] - prices[p.getKey()]));
	}
}
			

• Divide-and-Conquer, T(n) = 2T(n/2) + n
• O(nlgn)

import javafx.util.*;

public class S
{
	public static Tuple findMaxSubArray(int [] array, int low, int high)
	{
		if(high == low)
			return (new Tuple(low, high, array[low]));
		int leftLow, leftHigh, leftMax;
		int rightLow, rightHigh, rightMax;
		int crossLow, crossHigh, crossMax;

		int mid = (low+high)/2;
		Tuple leftT = findMaxSubArray(array, low, mid);
		Tuple rightT = findMaxSubArray(array, mid+1, high);
		Tuple crossT = findMaxCrossSubArray(array, low, mid, high);
		if(leftT.getMax() > rightT.getMax() && leftT.getMax() > crossT.getMax())
			return leftT;
		else if(rightT.getMax() > leftT.getMax() && rightT.getMax() > crossT.getMax())
			return rightT;
		else
			return crossT;
	}

	public static Tuple findMaxCrossSubArray(int [] array, int low, int mid, int high)
	{
		int leftSum = Integer.MIN_VALUE;
		int sum = 0;
		int indexLeft = mid;
		for(int i = mid; i >= low; i--)
		{
			sum += array[i];
			if(sum > leftSum)
			{
				leftSum = sum;
				indexLeft = i;
			}
		}
		int rightSum = Integer.MIN_VALUE;
		sum = 0;
		int indexRight = mid+1;
		for(int i = mid+1; i <= high; i++)
		{
			sum += array[i];
			if(sum > rightSum)
			{
				rightSum = sum;
				indexRight = i;
			}
		}

		return (new Tuple(indexLeft, indexRight, leftSum+rightSum));
	}

	public static int [] getChange(int [] p)
	{
		int [] c = new int[p.length-1];

		for(int i = 0; i < p.length-1; i++)
			c[i] = p[i+1] - p[i];

		return c;
	}

	public static void display(int [] array)
	{
		for(int i = 0; i < array.length; i++)
			System.out.printf("%5d", array[i]);
		System.out.println();
	}

	public static void main(String args[])
	{
		int [] prices = {100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97};
		int [] change = getChange(prices);

		display(change);

		Tuple t = findMaxSubArray(change, 0, change.length-1);

		System.out.println("Low: "+t.getLeft()+" High: "+t.getRight()+" Max: "+t.getMax());
	}
}

class Tuple
{
	private int left, right, max;
	Tuple(int l, int r, int m)
	{
		left = l;
		right = r;
		max = m;
	}

	int getLeft() {return left;}
	int getRight() {return right;}
	int getMax() {return max;}
}
			

• Brute-force, O(n³)

import java.util.*;

public class M
{
	public static int [][] mul(int [][] A, int [][] B)
	{
		int array[][] = new int[A.length][A[0].length];

		for(int i = 0; i < array.length; i++)
			for(int j = 0; j < array[i].length; j++)
				for(int k = 0; k < array.length; k++)
					array[i][j] += A[i][k]*B[k][j];

		return array;
	}

	public static int [][] getMatrix(int n)
	{
		int array [][] = new int[n][n];
		Random r = new Random();

		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				array[i][j] = r.nextInt(10);

		return array;
	}

	public static void display(int [][] array)
	{
		for(int i = 0; i < array.length; i++)
		{
			for(int j = 0; j < array[i].length; j++)
				System.out.printf("%5d", array[i][j]);
			System.out.println();
		}
	}

	public static void main(String args[])
	{
		int A[][] = getMatrix(10);
		int B[][] = getMatrix(10);

		int array[][] = mul(A, B);
		display(array);
	}
}
			

• S1 = B12-B22
• S2 = A11+A12
• S3 = A21+A22
• S4 = B21-B11
• S5 = A22+A22
• S6 = B11+B22
• S7 = A12-A22
• S8 = B21+B22
• S9 = A11-A21
• S0 = B11+B12

• P1 = A11*S1
• P2 = S2*B22
• P3 = S3*B11
• P4 = A22*S4
• P5 = S5*S6
• P6 = S7*S8
• P7 = S9*S0

• C11 = P5+P4-P2+P6
• C12 = P1+P2
• C12 = P3+P4
• C22 = P5+P1-P3-P7

• T(n) = 7T(n/2) + Θ(n²)

• CLRS Chapter 4