1. < -> n^(log_b(a))
2. n^(log_b(a)) * log(n)^d -> n^(log_b(a)) * log(n)^(d+1)
3. > -> f(n)

1. State the problem as formally as possible.
2. Identify sub-problems.
3. Find and prove correct a self-reduction from the problem to one or more of its sub-problems.
4. Identify overlapping sub-problems.
5. Select an appropriate data structure to store the solutions to sub- problems (usually an array).
6. Design an iterative algorithm that solves the sub-problems from easiest (smallest) to hardest (largest) using the self-reduction and stores their solutions in the data structure.
7. Analyse the runtime of the algorithm.
8. It is often easier to compute a minimum or maximum value first, and then recover the solution meeting that minimum or maximum.

1. A problem has the greedy choice property for a particular locally optimal choice if making the locally optimal choice leads to a globally optimal solution to the problem.
2. Making a greedy choice is another means of reducing a problem to a subproblem.
3. Unlike Dynamic Programming the greedy choices will not be reconsidered in a greedy algorithm.
4. There is often more than one greedy choice we might make locally.
5. Some of these choices will have the greedy choice property whereas others will not.
6. Counterexample: To prove the greedy choice is incorrect we need only find an instance of the problem that it does not work on.
7. Proof of Correctness: To prove the greedy choice correct we use a form of induction.

Often a greedy or dynamic programming approach solves the graph problem, but not always.

• Prim
• Kruskal
• Dijkstra