JCF Time Complexities Flashcards
1
Q
ArrayList: set(i, x)
A
O(1)
1
Q
ArrayList: get(i)
A
O(1)
2
Q
ArrayList: add(i, x)
A
O(1+n-i)
3
Q
ArrayList: remove(i)
A
O(n-i)
4
Q
LinkedList: all operations
A
O(1+min{i,n-i})
5
Q
HashSet: all operations
A
O(1)
6
Q
TreeSet: all operations
A
O(logn)
7
Q
TreeSet(Sorted): all operations
A
O(logn)
8
Q
HashMap: all operations
A
O(1)
9
Q
TreeMapp^3: all operations
A
O(logn)
10
Q
ArrayDeque: all operations
A
O(1)
11
Q
LinkedList(Deque): all operations
A
O(1)
12
Q
ArrayDeque(Queue): all operations
A
O(1)
13
Q
LinkedList(Queue): all operations
A
O(1)
14
Q
PrioityQueue: add(x)
A
O(logn)
15
Q
PrioityQueue: remove()
A
O(logn)
16
Q
PrioityQueue: element()
A
O(1)
17
Q
sort(list):
A
O(nlogn)
18
Q
min(c)/max(c):
A
O(n)
19
Q
reverse(list):
A
O(n)
20
Q
binarySearch(list, x):
A
O(logn)
