Major Algorithms

Question 1

Depth First Search, DFS (Time)

Answer 1

Worst is O(|E| + |V|) for Edges and Vertices

Question 2

Depth First Search, DFS (Space)

Answer 2

Worst is O(|V|) for Vertices

Question 3

Breadth First Search, BFS (Time)

Answer 3

Worst is O(|E| + |V|) for Edges and Vertices

Question 4

Breadth First Search, BFS (Space)

Answer 4

Worst is O(|V|) for Vertices

Question 5

Binary Search (sorted array of n elements) (Time)

Answer 5

Average is O(log(n)) and worst is the same

Question 6

Binary Search (Space)

Answer 6

Worst is O(1)

Question 7

Linear (Brute Force) search of an array (Time)

Answer 7

Average and Worst are both O(n)

Question 8

Linear (Brute Force) search of an array (Space)

Answer 8

O(1)

Question 9

Shortest path by Dijkstra,

using a Min-heap as priority queue (Time)

Answer 9

Average and Worst are both O((|V| + |E|) log|V|) for Vertices and Edges

Question 10

Shortest path by Dijkstra,

using a Min-heap as priority queue (Space)

Answer 10

Worst case is O(|V|) for Vertices

Question 11

Shortest path by Dijkstra,

using an unsorted array as priority queue (Time)

Answer 11

Average and Worst are both O(|V|^ 2) for the Vertices

Question 12

Shortest path by Dijkstra,

using an unsorted array as priority queue (Space)

Answer 12

Worst is O(|V|) for the Vertices

Question 13

Shortest path by Bellman-Ford (Time)

Answer 13

Average and Worst are both O(|V| |E|)

Question 14

Shortest path by Bellman-Ford (Space)

Answer 14

Worst is O(|V|)

Question 15

Quicksort(Time)

Answer 15

Best and average are O(n log n) Worst is O(n^2)

Question 16

Quicksort (Space)

Answer 16

O(n) worst

Question 17

Mergesort (Time)

Answer 17

Average, best, and worst are all O(n log n)

Question 18

MergeSort (Space)

Answer 18

worst O(n)

Question 19

Heapsort (Time)

Answer 19

O(n log n)

Question 20

Heapsort (Space)

Answer 20

O(1)

Question 21

Bubble Sort (Time)

Answer 21

best O(n), average and worst are O(n^2)

Question 22

Bubble Sort (Space)

Answer 22

O(1)

Question 23

Insertion Sort (Time)

Answer 23

best O(n) and average/worst are O(n^2)

Question 24

Insertion Sort (Space)

Answer 24

O(1)

Question 25

Selection Sort (Time)

Answer 25

O(n^2)

Question 26

Selection Sort (Space)

Answer 26

O(1)

Question 27

Bucket Sort (Time)

Answer 27

O(n + k) for best and average, worst is O(n^2)

Question 28

Bucket Sort (Space)

Answer 28

O(nk)

Question 29

Radix Sort (Time)

Answer 29

O(nk)

Question 30

Radix Sort(Space)

Answer 30

O(n+k)