Let’s simplify Big O

Joshycsm
Joshycsm
Jun 20, 2020 · 3 min read
https://www.bigocheatsheet.com/
https://www.bigocheatsheet.com/

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/

The Startup

Medium's largest active publication, followed by +755K people. Follow to join our community.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store