Big-O Notation Explained – Data Structures & Sorting Algorithms (Complete Reference)
1. What is Big‑O Notation?
Big‑O notation describes how an algorithm scales as input size n grows.
Time Complexity → How long an operation takes
Space Complexity → How much extra memory is used
Common Notations
| Notation | Meaning | Example |
|---|---|---|
| O(1) | Constant | Array index access |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Loop through array |
| O(n log n) | Linearithmic | Efficient sorting |
| O(n²) | Quadratic | Nested loops |
2. Common Data Structure Operations
📊 Table: Time & Space Complexity (All Columns Covered)
3. Explanation with Examples
Array
Access O(1):
arr[10]Insert/Delete O(n): shifting elements
Use case: Fast reads, static data
Stack (LIFO)
Insert/Delete O(1): push/pop
Search O(n): scan all elements
Use case: Undo, recursion, JVM stack
Queue (FIFO)
Insert/Delete O(1): enqueue/dequeue
Use case: Kafka, task scheduling
Hash Table
Average O(1): hash-based lookup
Worst O(n): collision chain
Use case: Caching, indexing
Balanced Trees (AVL / Red‑Black)
Guaranteed O(log n)
Use case: Sorted data (TreeMap)
4. Array Sorting Algorithms
📊 Table: Sorting Time & Space Complexity
| Algorithm | Time Complexity (Best) | Average | Worst | Space (Worst) |
|---|---|---|---|---|
| Quicksort | Ω(n log n) | Θ(n log n) | O(n²) | 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²) | O(n²) | O(1) |
| Insertion Sort | Ω(n) | Θ(n²) | O(n²) | O(1) |
| Selection Sort | Ω(n²) | Θ(n²) | O(n²) | O(1) |
| Counting Sort | Ω(n+k) | Θ(n+k) | O(n+k) | O(k) |
| Radix Sort | Ω(nk) | Θ(nk) | O(nk) | O(n+k) |
5. How to Choose the Right One
| Requirement | Best Choice |
|---|---|
| Fast lookup | HashMap |
| Sorted data | TreeMap / AVL |
| Large dataset sort | Merge / TimSort |
| Memory constrained | HeapSort |
| Messaging | Queue |
6. Interview‑Ready Summary
Arrays → Fast access
Linked Lists → Fast insertion
Hash Tables → Fast lookup
Trees → Ordered & scalable
O(n log n) → Optimal sorting
No comments:
Post a Comment