Big O Notation
Data structure & Algorithm

Array
Operation | Average Time Complexity |
Search | O(n) |
Search (sorted array) | O(log(n)) |
Insert | O(n) |
Insert (at the end) | O(1) |
Remove | O(n) |
Remove (at the end) | O(1) |
String
Operation | Average Time Complexity |
Access | O(1) |
Search | O(n) |
Insert | O(n) |
Remove | O(n) |
Hash Table
Operation | Average Time Complexity |
Search | O(1) |
Insert | O(1) |
Remove | O(1) |
Sort & Search
Algorithm | Average Time Complexity | Worst Time Complexity | Worst Space Complexity |
Bubble sort | O(n^2) | O(n^2) | O(1) |
Insertion sort | O(n^2) | O(n^2) | O(1) |
Selection sort | O(n^2) | O(n^2) | O(1) |
Quicksort | O(n log(n)) | O(n^2) | O(log(n)) |
Mergesort | O(n log(n)) | O(n log(n)) | O(n) |
Heap sort | O(n log(n)) | O(n log(n)) | O(1) |
Bucket sort | O(n+k) | O(n^2) | O(n + k) |
Radix sort | O(nk) | O(nk) | O(n+k) |
- 適当な配列を
- Mergesortで実装してみる
- Quicksortで実装してみる
Recursion/Backtracking
Binary search
Linked Lists
Operation | Average Time Complexity |
Access | O(n) |
Search | O(n) |
Insert | O(1) |
Remove | O(1) |
Stack
Operation | Average Time Complexity |
Top/Peek | O(1) |
Push | O(1) |
Pop | O(1) |
Queue
Operation | Average Time Complexity |
Enqueue/Offer | O(1) |
Dequeue/Poll | O(1) |
Balanced binary tree
Operation | Average Time Complexity |
Access | O(log(n)) |
Search | O(log(n)) |
Insert | O(log(n)) |
Remove | O(log(n)) |