Let’s simplify Big O
It’s good to understand how Big O gets calculated. But you can just follow a set of rules! When we talk about Big O, you will give one of these answers:
- O(n!), O(2^n), O(n^2), O(n log n), O(n), O(log n), O(1)
We can follow a Rule Book:
- Rule 1: Worst Case
- Rule 2: Remove Constants
- Rule 3: Different terms for inputs
- Rule 4: Drop Non Dominants
Lets explain what this means in more detail:
Big O Rule 1 (Worst Case)
- In JavaScript we can have a special line of code afterwards “break”!
- This code has been made more efficient so it will not loop through every element in an array.
- Big O only cares about the worst case. Say.. the element we are trying to locate is at the very end of an array versus the beginning of one with 10 elements. Still going to run 10 times versus 4 or 1.
- 10 loops. Still Big O(n)
- Always care about the worst case scenario. When we talk about scalability we have to consider this always! In the grand scheme of things since we can’t be certain what the input is we can only assume this is Big O(n) which is linear time.
- Big O doesn’t care, even if function is made more efficient with a break before end of loop.
Big O Rule 2 (Remove Constants)
- Math.floor will help get a whole number. i.e. var middleIndex = Math.floor(items.length / 2)
- O(1 + n/2 + 100) takes into consideration the Big O for each step. So this would simplify to just O(n)
- Doesn’t matter, just drop the constants.
- A function can have two separate steps which is to O(n) which would equate to O(2n) but it doesn’t matter since we drop the constants. So it really just becomes O(n).
- We don’t care how steep the line is just how the line moves as our inputs increase.
- with a x (element) and y (operations) graph.
Big O Rule 3 (Different terms for inputs)
- Trickiest part of an interview until you understand this rule.
- O(a + b) when you have two different inputs even when they are looping one after another
- What about a nested loop????
Big O Rule 4 (Drop Non Dominants)
- for loop has O(n) another for loop will add + this one has two for loops nested so n²
- drop non dominant terms! O(n + n²) => O(n²)
- WE care about the most dominant term.
- three nested loops or more is usually a really bad idea… probably a better way. Non-efficient. Slow running programming.
Big O Cheat Sheet
A few unmentioned will come up when we discuss data structures and algorithms:
- O(log N) — Logarithmic — usually searching algorithms have log(n) if they are sorted (Binary search)
- O(n*log(n)) Log Linear — Sorting operations usually
- O(2^N) Exponential — recursive algorithms that solve a problem of size N
- O(n!) — you are adding a loop for every element!
Iterating through half a collection is still O(n)
Two separate collections: O(a * b)
What can cause time in a function
- Operations (+, -, *, /)
- Comparisons ( <, >, ==)
- Looping (for, while)
- Outside Function call (function()) => a function inside of a function
Rule Book
- Always worst Case
- Remove Constants
- Different inputs should have different variables. O(a+b). A and B arrays nested would be O(a*b); + for steps in order, * for nested steps
- Drop Non-dominant terms; most dominant term is gonna be the most important thing affecting your code in terms of Big O.
What causes Space complexity?
- Variables
- Data Structures
- Function Call
- Allocations
I highly recommend Andrei Neagoie and all his Zero to Mastery Courses in order to gain the fundamentals to becoming a great programmer and to become a senior developer.
Photo credit: https://www.bigocheatsheet.com/
