Asymptotic Analysis

Ex: Given a sorted array, determine if the array contains any duplicates.
- Silly approach: Check every element to each other, quadratic time.
- Better approach: Compare each element with the element after itself, linear time.
To measure efficiency of a program:
- Define a metric to evaluate the efficiency. Can be runtime, memory, etc.
- Provide a mathematical function to classify the algorithm.

Techniques for Measuring Program Efficiency

We could physically measure the time it takes for the program to run.
- However, different computers have different runtimes.
- Different programming languages also have different efficiencies.
- We want to measure the inherent efficiency of the algorithm itself.
We can count the possible operations for an algorithm.
- Machine independent and also tells us how algorithm grows.
- The granularity of the operations also matters.
- Tedious to calculate and not a function.
For each input size N, select one specific input to represent that input size. Count the number of operations for that input.
- Common choises are the worst case input (the input that takes the most operations) and the best case input (the input that takes the least operations).
- This is now a function, but it’s still not too easy to compare between different algorithms. hewo

Program efficiency really only cares about order of growth, or about how efficiency scales.
For smaller inputs, O(N^2) may be faster than O(N) based on constants, but eventually O(N^2) will overtake O(N).
If we add up all of the general number of operations for some program, the term with the highest order dominantes over all other terms
- Ex: 0.0000001*2^N+23324234234N^2+123123123N+1230092108301820381923
- Is still a 2^N Order of growth algorithm.
We may group together all algorithms of a certain order of growth for their worst case efficiency into the Big-Theta notation.
- ϴ(1), ϴ(N), ϴ(N^2), ϴ(2^N), ϴ(logN), ϴ(NlogN), ϴ(N!)