Data Structures Time Complexity Cheat Sheet for Interviews
Data Structures Time Complexity Cheat Sheet for Interviews
Arrays: Access O(1), Search O(n), Insert O(n), Delete O(n)
Linked List: Access O(n), Search O(n), Insert O(1), Delete O(1)
Stack/Queue: Push/Pop O(1), Search O(n)
Hash Table: Search O(1) avg, Insert O(1) avg, Delete O(1) avg
BST: Search O(log n), Insert O(log n), Delete O(log n)
Heap: Insert O(log n), Delete O(log n), Find Min/Max O(1)
Sorting complexities:
Bubble/Selection/Insertion: O(n2)
Merge Sort: O(n log n) always
Quick Sort: O(n log n) avg, O(n2) worst
Heap Sort: O(n log n)
Searching:
Linear Search: O(n)
Binary Search: O(log n)
Always mention both time AND space complexity in interviews. Interviewers love candidates who think about optimization.
Knowing time complexities is crucial for interviews. Quick reference:
Arrays: Access O(1), Search O(n), Insert O(n), Delete O(n)
Linked List: Access O(n), Search O(n), Insert O(1), Delete O(1)
Stack/Queue: Push/Pop O(1), Search O(n)
Hash Table: Search O(1) avg, Insert O(1) avg, Delete O(1) avg
BST: Search O(log n), Insert O(log n), Delete O(log n)
Heap: Insert O(log n), Delete O(log n), Find Min/Max O(1)
Sorting complexities:
Bubble/Selection/Insertion: O(n2)
Merge Sort: O(n log n) always
Quick Sort: O(n log n) avg, O(n2) worst
Heap Sort: O(n log n)
Searching:
Linear Search: O(n)
Binary Search: O(log n)
Always mention both time AND space complexity in interviews. Interviewers love candidates who think about optimization.
This cheat sheet is a must-bookmark for interview prep! Understanding not just the values but WHY each complexity is what it is will help you answer follow-up questions. Also remember to consider space complexity alongside time complexity - interviewers often ask about trade-offs between the two. Great reference material!
1 Guest(s)
1 Guest(s)