Analyzing the time and space complexity of operations in various data structures is crucial for understanding their performance characteristics and making informed decisions based on your application’s requirements.
1. Array
| Operation | Time Complexity |
|---|---|
| Access (by index) | O(1) |
| Search (unsorted) | O(n) |
| Search (sorted, using binary search) | O(log n) |
| Insertion/Deletion (at end, if space) | O(1) |
| Insertion/Deletion (at beginning/middle) | O(n) |
Space Complexity: O(n)
2. Linked List
| Operation | Time Complexity |
|---|---|
| Access (by index) | O(n) |
| Search | O(n) |
| Insertion/Deletion (at beginning) | O(1) |
| Insertion/Deletion (at end, with tail) | O(1) |
| Insertion/Deletion (middle, after traversal) | O(n) |
Space Complexity: O(n)
3. Stack
| Operation | Time Complexity |
|---|---|
| Push (Insertion) | O(1) |
| Pop (Removal) | O(1) |
| Peek (Access top) | O(1) |
Space Complexity: O(n)
4. Queue
| Operation | Time Complexity |
|---|---|
| Enqueue (Insertion) | O(1) |
| Dequeue (Removal) | O(1) |
| Peek (Access front) | O(1) |
Space Complexity: O(n)
5. HashMap / HashSet
| Operation | Time Complexity |
|---|---|
| Insertion | O(1) average, O(n) worst |
| Deletion | O(1) average, O(n) worst |
| Search | O(1) average, O(n) worst |
| Iteration over entries | O(n) |
Space Complexity: O(n)
6. TreeMap / TreeSet
| Operation | Time Complexity |
|---|---|
| Insertion | O(log n) |
| Deletion | O(log n) |
| Search | O(log n) |
| Iteration (in order) | O(n) |
Space Complexity: O(n)
7. PriorityQueue
| Operation | Time Complexity |
|---|---|
| Insertion | O(log n) |
| Removal (peek and remove) | O(log n) |
| Search | O(n) |
Space Complexity: O(n)
8. HashTable / ConcurrentHashMap
| Operation | Time Complexity |
|---|---|
| Insertion | O(1) average, O(n) worst |
| Deletion | O(1) average, O(n) worst |
| Search | O(1) average, O(n) worst |
| Iteration over entries | O(n) |
Space Complexity: O(n)
Summary of Complexities
Big-O Time Complexities
| Notation | Name | Description |
|---|---|---|
| O(1) | Constant Time | Executes in the same time regardless of input size. |
| O(log n) | Logarithmic Time | Common in divide-and-conquer algorithms and balanced trees (e.g., BST search). |
| O(n) | Linear Time | Time increases linearly with input size. |
| O(n log n) | Log-linear Time | Typical of efficient sorting algorithms like Merge Sort and Heap Sort. |
| O(n²) | Quadratic Time | Seen in algorithms with nested loops (e.g., Bubble Sort). |
| O(2^n) | Exponential Time | Drastically increases with input size; common in brute-force recursive solutions. |
Understanding these complexities helps in choosing the appropriate data structure based on the specific requirements of your application, ensuring optimal performance and efficient use of resources. It’s important to consider trade-offs between time and space complexities, as well as the typical operations your application will perform most frequently.