10 Common Complexities
Algorithms
Algorithm | Time Complexity |
Binary Search on array | O(logN) |
Reversing a string | O(len) |
Linear search | O(N) |
Compare Nth fibonacci number | O(N) |
Compare two strings | O(min(Len1, Len2)) |
Check if a string is palindrome | O(N) |
Sorting (merge sort, quick sort avg, heap sort) | O(nlogn) |
Sorting (bubble sort, quick sort worst etc.) | O(n^2) |
Two nested loop | O(n^2) |
Strstr | O(n * m) / KMP O(n + m) |
Subsets | O(2^n) |
Permutations | O(n!) |
Data Structure
TreeMap | Heap | PriorityQueue | |
Insert | logn | logn | logn |
delete任意node | logn | logn | X |
pop (移除顶点） | logn | logn | logn |
find | long | logn | X |
modify | logn | logn | X |
min/max (peek) | logn | O(1) | O(1) |
upperbound/lowerbound | logn | X | X |
ArrayList | LinkedList | |
set(index) | O(1) | O(n) |
add(E) | O(n) | O(1) |
add(E, index) | O(n) | O(n) |
remove(index) | O(n) | O(n) |
Iterator.remove() | O(n) | O(1) |
Iterator.add(E) | O(n) | O(1) |
Power of 2 table
Power of 2 | Exac Value(X) | Approximate value | X Bytes into MB, GB, etc |
7 | 128 | ||
8 | 256 | ||
10 | 1024 | 1 thousand | 1KB |
16 | 65,535 | 64KB | |
20 | 1,048,576 | 1 million | 1MB |
30 | 1,073,741,824 | 1 billion | 1GB |
32 | 4,294,967,296 | 4GB | |
40 | 1,099,511,627,776 | 1 trillion | 1TB |
Last updated
