MetoolzyBig O Cheat Sheet
Complexity Growth Chart
Sorting Algorithms
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) | Yes |
| Tim Sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes |
Data Structure Operations
Each cell shows Average / Worst case complexity.
| Data Structure | Access | Search | Insert | Delete |
|---|---|---|---|---|
| Array | O(1)/O(1) | O(n)/O(n) | O(n)/O(n) | O(n)/O(n) |
| Stack | O(n)/O(n) | O(n)/O(n) | O(1)/O(1) | O(1)/O(1) |
| Queue | O(n)/O(n) | O(n)/O(n) | O(1)/O(1) | O(1)/O(1) |
| Linked List | O(n)/O(n) | O(n)/O(n) | O(1)/O(1) | O(1)/O(1) |
| Hash Table | —/— | O(1)/O(n) | O(1)/O(n) | O(1)/O(n) |
| BST | O(log n)/O(n) | O(log n)/O(n) | O(log n)/O(n) | O(log n)/O(n) |
| AVL Tree | O(log n)/O(log n) | O(log n)/O(log n) | O(log n)/O(log n) | O(log n)/O(log n) |
| B-Tree | O(log n)/O(log n) | O(log n)/O(log n) | O(log n)/O(log n) | O(log n)/O(log n) |
| Red-Black | O(log n)/O(log n) | O(log n)/O(log n) | O(log n)/O(log n) | O(log n)/O(log n) |
Common Algorithms
| Algorithm | Time | Space |
|---|---|---|
| Binary Search | O(log n) | O(1) |
| BFS | O(V+E) | O(V) |
| DFS | O(V+E) | O(V) |
| Dijkstra | O((V+E)log V) | O(V) |
| Bellman-Ford | O(VE) | O(V) |
| Floyd-Warshall | O(V³) | O(V²) |
Interactive Chart
Hover over the growth chart to compare operations at any input size.
Common Complexities
O(1) to O(n!) — all major complexity classes with color-coded badges.
Code Examples
Sorting algorithms, data structures, and graph algorithms at a glance.
Comparison
Side-by-side tables for best, average, worst case and space complexity.
Giới thiệu về Big O Cheat Sheet
The Big O Notation Cheat Sheet is a comprehensive reference for algorithm and data structure time and space complexity. Big O notation describes how an algorithm's performance scales with input size — understanding it is essential for writing efficient code, passing technical interviews, and making informed architectural decisions. This tool provides an interactive growth chart where you can hover to compare how many operations different complexity classes require at any input size, plus reference tables for 9 sorting algorithms, 9 data structures, and 6 common graph and search algorithms. Each entry shows best, average, and worst-case time complexity and space complexity with colour-coded badges from green (efficient O(1), O(log n)) to red (avoid O(n²), O(2ⁿ)). Stability of sorting algorithms is also noted.
Làm sao để Big O Cheat Sheet?
- Hover over the Complexity Growth Chart to see the exact operation count for each complexity class at a given input size n.
- Study the colour coding: green = fast (O(1), O(log n)), yellow = acceptable (O(n)), orange = moderate (O(n log n)), red = slow (O(n²), O(2ⁿ)).
- Use the Sorting Algorithms table to compare sorting choices — remember Quick Sort has O(n²) worst case while Merge Sort guarantees O(n log n).
- Use the Data Structures table to choose the right structure — Hash Tables give O(1) average search but O(n) worst case; AVL Trees guarantee O(log n) for all operations.
- Check the Common Algorithms section for standard graph algorithm complexities (BFS, DFS, Dijkstra, Floyd-Warshall).
- Use the Stable column when selecting a sort for data where the order of equal elements matters.
Câu hỏi thường gặp
What is Big O notation and why does it matter?
Big O notation describes the upper bound of how an algorithm's runtime or memory usage grows as the input size n increases. It matters because an algorithm that works fine for 100 items may be completely unusable for 1,000,000 items. O(n²) at n=1000 means 1,000,000 operations; O(n log n) at n=1,000,000 means only ~20,000,000 — a 50× difference that becomes billions× at larger scales.
What is the difference between time complexity and space complexity?
Time complexity measures how the number of operations grows with input size. Space complexity measures how much extra memory the algorithm needs. For example, Merge Sort has O(n log n) time but O(n) space because it needs a temporary copy of the array. In-place algorithms like Heap Sort use O(1) extra space at the cost of more complex implementation.
Why does Hash Table have O(n) worst-case search?
Hash Tables achieve O(1) average search because keys are distributed across buckets using a hash function. In the worst case (a very poor hash function or many hash collisions), all keys end up in the same bucket, degenerating into a linked list with O(n) search. Good hash functions and load factor management (rehashing) keep the average near O(1).
When should I choose Merge Sort over Quick Sort?
Choose Merge Sort when: (1) you need guaranteed O(n log n) worst-case performance and cannot afford the O(n²) worst case of Quick Sort on sorted or adversarially chosen input, (2) you need a stable sort, or (3) you are sorting linked lists where random access is expensive. Choose Quick Sort when average performance matters more and you want in-place sorting with low cache miss rates.
What is amortized complexity and how does it relate to Big O?
Amortized complexity describes the average cost per operation over a sequence of operations, even if individual operations occasionally take longer. For example, dynamic arrays (like JavaScript arrays or Python lists) have O(1) amortized push even though they occasionally need O(n) to resize and copy — because resizes happen infrequently enough that the average cost per push is still O(1).
Công cụ liên quan
Top 10 Free Tools Every Developer Needs
Boost your productivity instantly. Get our exclusive cheatsheet featuring the most essential web utilities you didn't know you needed, delivered straight to your inbox.
We respect your inbox. Unsubscribe at any time.
Giải Pháp Toàn Diện: Big O Cheat Sheet Tốt Nhất
Big O Cheat Sheet là một công cụ trực tuyến miễn phí, mạnh mẽ được thiết kế để đơn giản hóa quy trình làm việc kỹ thuật số của bạn. Tra cứu độ phức tạp thời gian và không gian cho thuật toán và cấu trúc dữ liệu.
Trong kỷ nguyên số, hiệu suất làm việc là yếu tố quyết định thành công. Dù bạn là lập trình viên, nhà thiết kế hay marketer, việc tìm kiếm các công cụ đáng tin cậy là rất quan trọng. Với Big O Cheat Sheet của chúng tôi, bạn có thể hoàn thành công việc ngay lập tức trên trình duyệt mà không cần đăng ký tài khoản.
Tại sao nên sử dụng Big O Cheat Sheet của chúng tôi?
Công cụ của chúng tôi được xây dựng với ưu tiên hàng đầu về hiệu suất và quyền riêng tư. Tốc độ xử lý cực nhanh giúp bạn tiết kiệm tối đa thời gian.
- Miễn phí 100%: Không có phí ẩn, không giới hạn tính năng.
- Không cần cài đặt: Hoạt động mượt mà trên mọi trình duyệt web hiện đại.
- Bảo mật tuyệt đối: Tôn trọng dữ liệu của bạn. Quá trình xử lý diễn ra an toàn.
- Dễ sử dụng: Giao diện trực quan, thân thiện với cả những người không rành kỹ thuật.
Nâng cao hiệu suất làm việc
Việc tích hợp Big O Cheat Sheet vào công việc hàng ngày sẽ giúp bạn tiết kiệm rất nhiều thời gian. Thay vì phải tải xuống các phần mềm nặng nề, bạn chỉ cần đánh dấu (bookmark) trang này và giải quyết vấn đề chỉ trong vài cú click chuột.
Hãy trải nghiệm ngay hôm nay!
Top 10 Free Tools Every Developer Needs
Boost your productivity instantly. Get our exclusive cheatsheet featuring the most essential web utilities you didn't know you needed, delivered straight to your inbox.
We respect your inbox. Unsubscribe at any time.