Big O of Literally Everything Flashcards
1
Q
Stack.push()
A
O(1)
2
Q
Stack.pop()
A
O(1)
3
Q
Stack.peek()
A
O(1)
4
Q
Stack.contains()
A
O(n)
5
Q
Queue.enqueue()
A
O(1)
6
Q
Queue.dequeue()
A
O(1)
7
Q
Queue.contains()
A
O(n)
8
Q
Single/ doubly linked list
.add()
A
O(1)
9
Q
Singly/ doubly linked list
.remove()
A
O(1)
10
Q
Singly/ double linked list
.contains()
A
O(n)
11
Q
Quicksort
A
N^2
12
Q
Mergesort
A
NlogN
13
Q
Heapsort
A
NlogN
14
Q
Insertion sort
A
N^2
15
Q
Selection sort
A
N^2
16
Q
Bucket sort
A
N^2
17
Q
dijkstra
A
sparse
O(EV)
dense
O(V^2)
18
Q
prims algorithm
A
V^2 without heaps, ElogV with heaps
19
Q
kruskals algorithm
A
O(ElogV)
20
Q
binary tree insert
A
O(n)
21
Q
binary tree delete
A
O(n)
22
Q
binary contains
A
O(n)
23
Q
avl tree rotation
A
zig zig find where the imbalance is by starting at the bottom (wherever you find the imbalance is where the node will be switched) if its at the root first fix the imbalance at the bottom then pull something else up to the root
