Algorithms and Big O Notation

This type of algorithm iterates through the problem space taking the optimal solution "so far," until it reaches the end.

This means stitching together optimal solutions to subproblems yields an optimal solution (Used in context with greedy algorithms).

This approach to greedy algorithms is true only if the problem has "optimal substructure".

This is a way to measure how well a computer algorithm scales as the amount of data involved increases.

Speed and How well the algorithm scales.

This algorithm will perform the same no mater how much data it has, or how large the amount of data is.

This big O notation is read: "Order of N".

Algorithm where time to complete will grow in direct proportion to the amount of data. Example is traversing the entirety of a linear array.

Algorithm where time to complete will be proportionate to the the square of the amount of data. An example is the Bubble Sort, which has NESTED ITERATIONS -- which hampers performance.

When  the amount of data is decreased roughly by 50% each time through the algorithm. Running the binary search will show that increasing the amount of data has very little effect on the completion time of the algorithm.

Quick sort falls into this order. The trick here is these values are only going to be compared ONCE. In mathematical terms the number of comparisons is equal to log n! Another way of looking at this would be Comparisons = log n + log(n-1)+.....+ log(1). The idea is we stop at log(1).

• 1. O(n!) terrible
• 2. O(2n) terrible
• 3. O(n2) terrible
• 4. O(n log n) bad
• 5. O(n)  fair
• 6. O(log n), O(1) excellent