www.bigocheatsheet.com Open in urlscan Pro
107.180.47.5  Public Scan

Form analysis
0 forms found in the DOM

Text Content

Big-O Cheat Sheet Download PDF
188k Shares
Tweet
Share
Share
Share


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 Uber, 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

AngularJS to React Automated Migration


BIG-O COMPLEXITY CHART

Horrible Bad Fair Good Excellent

O(log n), O(1) O(n) O(n log n) O(n^2) O(2^n) O(n!) Operations Elements



COMMON DATA STRUCTURE OPERATIONS

Data Structure Time Complexity Space Complexity Average Worst Worst Access
Search Insertion Deletion Access Search Insertion Deletion Array Θ(1) Θ(n) Θ(n)
Θ(n) O(1) O(n) O(n) O(n) O(n) Stack Θ(n) Θ(n) Θ(1) Θ(1) O(n) O(n) O(1) O(1) O(n)
Queue Θ(n) Θ(n) Θ(1) Θ(1) O(n) O(n) O(1) O(1) O(n) 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 Table N/A Θ(1) Θ(1) Θ(1) N/A O(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 Tree N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) N/A O(n) O(n) O(n) O(n)
B-Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(log(n)) O(log(n)) O(log(n))
O(log(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 Tree N/A Θ(log(n)) Θ(log(n)) Θ(log(n))
N/A O(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

Algorithm Time Complexity Space Complexity Best Average Worst Worst 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

   
   
 * Cracking the Coding Interview: 150 Programming Questions and Solutions
 * Introduction to Algorithms, 3rd Edition
 * Data Structures and Algorithms in Java (2nd Edition)
 * High Performance JavaScript (Build Faster Web Application Interfaces)


GET THE OFFICIAL BIG-O CHEAT SHEET POSTER


CONTRIBUTORS

 1.  Eric Rowell
 2.  Quentin Pleple
 3.  Michael Abed
 4.  Nick Dizazzo
 5.  Adam Forsyth
 6.  Felix Zhu
 7.  Jay Engineer
 8.  Josh Davis
 9.  Nodir Turakulov
 10. Jennifer Hamon
 11. David Dorfman
 12. Bart Massey
 13. Ray Pereda
 14. Si Pham
 15. Mike Davis
 16. mcverry
 17. Max Hoffmann
 18. Bahador Saket
 19. Damon Davison
 20. Alvin Wan
 21. Alan Briolat
 22. Drew Hannay
 23. Andrew Rasmussen
 24. Dennis Tsang
 25. Vinnie Magro
 26. Adam Arold
 27. Alejandro Ramirez
 28. Aneel Nazareth
 29. Rahul Chowdhury
 30. Jonathan McElroy
 31. steven41292
 32. Brandon Amos
 33. Joel Friedly
 34. Casper Van Gheluwe
 35. Eric Lefevre-Ardant
 36. Oleg
 37. Renfred Harper
 38. Piper Chester
 39. Miguel Amigot
 40. Apurva K
 41. Matthew Daronco
 42. Yun-Cheng Lin
 43. Clay Tyler
 44. Orhan Can Ozalp
 45. Ayman Singh
 46. David Morton
 47. Aurelien Ooms
 48. Sebastian Paaske Torholm
 49. Koushik Krishnan
 50. Drew Bailey
 51. Robert Burke


MAKE THIS PAGE BETTER

Edit these tables!


Please enable JavaScript to view the comments powered by Disqus.