Big O Flashcards
Big O notation focuses on…
developing scalable code
What is Big O notation?
it is the upper bound, or worst case, measurement that defines how quickly or slow an algorithm’s runtime increases as inputs increase.
Big O notation is used as a measurement to inform us how efficient our algorithm is and how well it will scale.
How to measure Big O of an algorithm?
count the operations, then count the number of input elements. Then count the total amount of operations.
What is the overview of Big O ratings?
Constant time: excellent
linear time: fair
How can we simplify Big O notation?
With these 4 rules:
- Worse Case
- Remove Constants
- Different terms for inputs
- Drop Non Dominants
Rule #1: Worst Case
When calculating Big O we always think in terms of the Worst Case.
Rule #2: Remove Constants
Big O is more of a big picture analysis. Will the scale well or will it scale poorly?
We do not need to know the intricate, decimal point calculation… yet..
So, we remove the constants.
example: O(2n) becomes O(n)
O(3 + n) becomes O(n)
O(7) becomes O(1)
Rule #3: Different terms for different inputs
if there are more than one input into the function/algorithm, then the Big O of that algorithm should be expressed in reference to those terms.
example:
def call_friends_and_family(family_group, friend_group):
loop over family_group, then call each person by one
loop over friend_group, then call each person one by one
The Big O of this program would be expressed as: O(a + b), rather than O(n)
Rule #4: Drop Non Dominants
We focus on the most impactful items.
Example: O(n + n^2) would become O(n)
What causes additional time in a function? aka what takes up processing time?
Operations
Comparisons
Looping
Outside function calls
Why this matters?
The two principles of good programs are: 1) readability 2) scalability
When we develop a program we need to be thinking in terms of readability and scalability!
the right Data Structures + the right Algorithms = Good Programs
Data Structures are how we store information/data
Algorithms are how we interact with the data structures to create desired functionality to achieve desired output
Be obsessed with picking the right data structure and designing the right algorithm and your program will be good quality by default!
What are the 3 pillars of programming?
- Readability
- Memory aka Space Complexity
- Speed aka Time Complexity
Space Complexity: two ways to remember things
the Heap: where we store variables that was assign values to
the Stack: keep track of our function calls
What is Space Complexity?
Space complexity measures how much memory is being used relative to input. Space complexity focuses on ADDITIONAL SPACE needed as a result of the function.
What causes space complexity/takes up memory?
variables data structures function calls allocations
