Algorithm Complexities

Question 1

What is the best case time complexity of all searching algorithms?

Answer 1

O(1) (because it is the found at the first item examined)

Question 2

Average time complexity of a linear search?

Answer 2

O(n)

Question 3

Average time complexity of a binary search on an array?

Answer 3

O(log n)

Question 4

Average time complexity of a binary search on a tree?

Answer 4

O(log n)

Question 5

Average time complexity of a hashing algorithm?

Answer 5

O(1)

Question 6

Average time complexity of a breadth/depth first search

Answer 6

O(V + E) (vertices + edges, equivalent to O(n) )

Question 7

Worst case time complexity of a linear search?

Answer 7

O(n)

Question 8

Worst case time complexity of a binary search on an array?

Answer 8

O(log n)

Question 9

Worst case time complexity of a binary search on a tree?

Answer 9

O(n)

Question 10

Worst case time complexity of a hashing algorithm?

Answer 10

O(n) (because the value has been stored in the overflow table, so linear searches through all of its items)

Question 11

Worst case time complexity of a breadth/depth first search

Answer 11

O(V^2) (vertices^2)

Question 12

Best case time complexity of a bubble sort?

Answer 12

O(n)

Question 13

Best case time complexity of an insertion sort?

Answer 13

O(n)

Question 14

Time complexity in any case of a merge sort?

Answer 14

O(n log n)

Question 15

Best case time complexity of a quick sort?

Answer 15

O(n log n)

Question 16

Average time complexity of a bubble sort?

Answer 16

O(n^2)

Question 17

Average time complexity of an insertion sort?

Answer 17

O(n^2)

Question 18

Average time complexity of a quick sort?

Answer 18

O(n log n)

Question 19

Worst case time complexity of a bubble sort?

Answer 19

O(n^2)

Question 20

Worst case time complexity of an insertion sort?

Answer 20

O(n^2)

Question 21

Worst case time complexity of a quick sort?

Answer 21

O(n^2)

Question 22

Space complexity of a bubble sort?

Answer 22

O(1)

Question 23

Space complexity of an insertion sort?

Answer 23

O(1)

Question 24

Space complexity of a merge sort?

Answer 24

O(n)

Question 25

Space complexity of a quick sort?

Answer 25

O(log n)