Hey, Mom! The Explanation.

Here's the permanent dedicated link to my first Hey, Mom! post and the explanation of the feature it contains.

Wednesday, December 7, 2016

Hey, Mom! Talking to My Mother #519 - Big O Cheat Sheet

Hey, Mom! Talking to My Mother #519 - Big O Cheat Sheet

Hi Mom,

Here's some of what I am working on. My final exam in Discrete Math is one week from last night. I am devoting many hours to study between now and then. I have started earlier than I usually start, so I am proud of that jump start.

Today's post is just a dumping place for some of this material. I wish you were still here as I would explain it to you, and you would pretend to be interested.


Know Thy Complexities!

Hi there!  This webpage covers the space and time Big-O complexities of common algorithms used in Computer Science.  When preparing for technical interviews in the past, I found myself spending hours crawling the internet putting together the best, average, and worst case complexities for search and sorting algorithms so that I wouldn't be stumped when asked about them.  Over the last few years, I've interviewed at several Silicon Valley startups, and also some bigger companies, like Google, Facebook, Yahoo, LinkedIn, and eBay, and each time that I prepared for an interview, I thought to myself "Why hasn't someone created a nice Big-O cheat sheet?".  So, to save all of you fine folks a ton of time, I went ahead and created one.  Enjoy! Eric
If you're trying to catch them all, you might also check out the Pokemon Go Evolution Chart.

Big-O Complexity Chart

O(log n), O(1)O(n)O(n log n)O(n^2)O(2^n)O(n!)OperationsElements

Common Data Structure Operations

Data StructureTime ComplexitySpace Complexity
Singly-Linked ListΘ(n)Θ(n)Θ(1)Θ(1)O(n)O(n)O(1)O(1)O(n)
Doubly-Linked ListΘ(n)Θ(n)Θ(1)Θ(1)O(n)O(n)O(1)O(1)O(n)
Skip ListΘ(log(n))Θ(log(n))Θ(log(n))Θ(log(n))O(n)O(n)O(n)O(n)O(n log(n))
Hash TableN/AΘ(1)Θ(1)Θ(1)N/AO(n)O(n)O(n)O(n)
Binary Search TreeΘ(log(n))Θ(log(n))Θ(log(n))Θ(log(n))O(n)O(n)O(n)O(n)O(n)
Cartesian TreeN/AΘ(log(n))Θ(log(n))Θ(log(n))N/AO(n)O(n)O(n)O(n)
Red-Black TreeΘ(log(n))Θ(log(n))Θ(log(n))Θ(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(n)
Splay TreeN/AΘ(log(n))Θ(log(n))Θ(log(n))N/AO(log(n))O(log(n))O(log(n))O(n)
AVL TreeΘ(log(n))Θ(log(n))Θ(log(n))Θ(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(n)
KD TreeΘ(log(n))Θ(log(n))Θ(log(n))Θ(log(n))O(n)O(n)O(n)O(n)O(n)

Array Sorting Algorithms

AlgorithmTime ComplexitySpace Complexity
QuicksortΩ(n log(n))Θ(n log(n))O(n^2)O(log(n))
MergesortΩ(n log(n))Θ(n log(n))O(n log(n))O(n)
TimsortΩ(n)Θ(n log(n))O(n log(n))O(n)
HeapsortΩ(n log(n))Θ(n log(n))O(n log(n))O(1)
Bubble SortΩ(n)Θ(n^2)O(n^2)O(1)
Insertion SortΩ(n)Θ(n^2)O(n^2)O(1)
Selection SortΩ(n^2)Θ(n^2)O(n^2)O(1)
Tree SortΩ(n log(n))Θ(n log(n))O(n^2)O(n)
Shell SortΩ(n log(n))Θ(n(log(n))^2)O(n(log(n))^2)O(1)
Bucket SortΩ(n+k)Θ(n+k)O(n^2)O(n)
Radix SortΩ(nk)Θ(nk)O(nk)O(n+k)
Counting SortΩ(n+k)Θ(n+k)O(n+k)O(k)
CubesortΩ(n)Θ(n log(n))O(n log(n))O(n)

Learn More

Get the Official Big-O Cheat Sheet Poster


Reflect and connect.

Have someone give you a kiss, and tell you that I love you.

I miss you so very much, Mom.

Talk to you tomorrow, Mom.


- Days ago = 521 days ago

- Bloggery committed by chris tower - 1612.07 _ 10:10

NOTE on time: When I post late, I had been posting at 7:10 a.m. because Google is on Pacific Time, and so this is really 10:10 EDT. However, it still shows up on the blog in Pacific time. So, I am going to start posting at 10:10 a.m. Pacific time, intending this to be 10:10 Eastern time. I know this only matters to me, and to you, Mom. But I am not going back and changing all the 7:10 a.m. times. But I will run this note for a while. Mom, you know that I am posting at 10:10 a.m. often because this is the time of your death.
Post a Comment