2.3.1 algorithms

Question 1

what is worst case average case and best case for a linear search

Answer 1

O(n) O(n), O(1)

Question 2

what is worst case average case and best case for a Binary search

Answer 2

O(log(n)) O(log(n)) O(1)

Question 3

what is worst case average case and best case for a binary search tree

Answer 3

O(n), O(log(n)), O(1)

Question 4

what is worst case average case and best case for searching a hash table

Answer 4

O(n) O(1) O(1)

Question 5

what is worst case average case and best case for a breadth/depth of a graph

Answer 5

O(v^2) O(V+E) O(1)

Question 6

what is worst case average case and best case for a bubble sort

Answer 6

O(n^2) O(n^2) O(n)

Question 7

what is worst case average case and best case for a insertion sort

Answer 7

O(n^2) O(n^2) O(n)

Question 8

what is worst case average case and best case for a Merge sort

Answer 8

O(nlog(n)) O(nlog(n)) O(nlog(n))

Question 9

what is worst case average case and best case for quick sort

Answer 9

O(n*log(n)) O(nlog(n)) O(n^2)

Question 10

what is the space complexity of merge sort

Answer 10

O(n) (because it has to make temporary arays with a sieze proportional to the main array)

Question 11

what is the space complexity of quick sort

Answer 11

O(log(n)) (dont have to know but makes log(n) recursive calls and makes an array of fixed size each recursive call)

Question 12

what is the space complexity of bubble and insertion sort

Answer 12

O(1)