Big O of Literally Everything

Question 1

Stack.push()

Answer 1

O(1)

Question 2

Stack.pop()

Answer 2

O(1)

Question 3

Stack.peek()

Answer 3

O(1)

Question 4

Stack.contains()

Answer 4

O(n)

Question 5

Queue.enqueue()

Answer 5

O(1)

Question 6

Queue.dequeue()

Answer 6

O(1)

Question 7

Queue.contains()

Answer 7

O(n)

Question 8

Single/ doubly linked list

.add()

Answer 8

O(1)

Question 9

Singly/ doubly linked list

.remove()

Answer 9

O(1)

Question 10

Singly/ double linked list

.contains()

Answer 10

O(n)

Question 11

Quicksort

Answer 11

N^2

Question 12

Mergesort

Answer 12

NlogN

Question 13

Heapsort

Answer 13

NlogN

Question 14

Insertion sort

Answer 14

N^2

Question 15

Selection sort

Answer 15

N^2

Question 16

Bucket sort

Answer 16

N^2

Question 17

dijkstra

Answer 17

sparse
O(EV)

dense
O(V^2)

Question 18

prims algorithm

Answer 18

V^2 without heaps, ElogV with heaps

Question 19

kruskals algorithm

Answer 19

O(ElogV)

Question 20

binary tree insert

Answer 20

O(n)

Question 21

binary tree delete

Answer 21

O(n)

Question 22

binary contains

Answer 22

O(n)

Question 23

avl tree rotation

Answer 23

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