2.3.4 average time complexities of different searching algorithms

Question 1

Linear search

Answer 1

O(n)
Worst case is O(n)
Best case is O(1) (finding it instantly)

Question 2

Binary search (array)

Answer 2

O(log(n))
Worst case is O(log(n))
Best case is O(1)

Question 3

Binary search (tree)

Answer 3

O(log(n))
Worst case is O(n)
Best case is O(1)

Question 4

Hashing

Answer 4

O(1)
Worst case is O(n)
Best case is O(1)

Question 5

Breadth/depth first of graph

Answer 5

O(V+E) (number of vertices + number of edges)
Worst case is O(V^2) (number of vertices, squared)
Best case is O(1)