Guiding Principles of Analysis of Algorithms Flashcards
What is the goal of these three principles?
to identify a sweet spot for the analysis of algorithms, one that balances of accuracy and tractability
The goal of Analysis of Algorithms
to have predictive power about whether an algorithm will be fast or slow in practice
this will allow us to paint an accurate picture of which algorithms tend to run faster than others
1st Guiding Principle: Worst-Case Analysis
worst-case analysis makes no assumptions about the inputs and simply gives a running time bound that is valid even for the ‘worst’ inputs
2nd Guiding Principles: Bigger Picture
we should not worry about small constant factors or lower-order terms in running time bounds
discards certain information and maintains focus on the bigger picture goal: providing guidance as to which algorithms tend to be faster than others
3rd Guiding Principle: Asymptotic Analysis
focus on the rate of growth of an algorithm’s running time as input size n grows large
the reason we care about the scale or large inputs is because it is with large inputs that we require algorithmic ingenuity.
Most algorithms will suffice for simple problems with small inputs on a modern computer
Our 3 Guiding Principles lead us to the following definition of a fast algorithm:
is an algorithm whose worst-case running time grows slowly with input size
Big O is meant to help us look at time and space as
valuable, yet limited, resources that we must use wisely.
Big O is concerned with
- readability
- scalability (time or speed, space or memory)
Big O allows us to measure the idea of scalable code. This is bc there’s no such thing as a free lunch. Knowing how much time and memory your code uses is critical as both are expensive resources for your company.
Big O is used to describe how efficient we can run our code with respect to time and space
