Searching Algorithms

Question 1

What is Big-O notation?

Answer 1

It allows us to talk about the efficiency of an algorithm no matter what computer it is running on.

Question 2

What is time complexity?

Answer 2

It is based on the number of items the algorithm is executed on - it tells us how the time taken scales with the size of the problem.

Question 3

What are the types of time complexity?

Answer 3

Worst-case complexity - e.g. maximum time it could take to sort a list.

Best-case complexity - e.g. shortest possible time it could take to sort a list.

Average-case complexity: e.g. expected time it generally takes to sort a list.

Algorithmic time complexity always refers to the worst case.

Question 4

What is the time complexity of a linear search?

Answer 4

O(n)

Question 5

What is the time complexity of a binary search?

Answer 5

O(log n)

Question 6

What is the time complexity of a binary tree search?

Answer 6

O(log n)

Question 7

What is the time complexity of a bubble sort?

Answer 7

O(n^2)

Question 8

What is the time complexity of a merge sort?

Answer 8

O(n logn)

Question 9

What is the explanation of the time complexity for a linear search?

Answer 9

As the size of the list/problem increases, the time taken increases at the same rate. The worst/case scenario is that all n items will be visited (if the item is at the end).

Question 10

What is the explanation of the time complexity for a binary search?

Answer 10

Each comparison halves the size of the list that has to be searched through.
If the size of the list doubles then the number of comparisons needed only increases by 1.

Question 11

What are the disadvantages of a binary search?

Answer 11

It requires the list to be ordered. This takes time and is reliant on an efficient sorting algorithm.

Question 12

What is the explanation of the time complexity for a bubble sort?

Answer 12

For n items in the list:

The algorithm makes (at most) n passes though the list.
On each pass it examines n items.
There are (n)(n) operations in total.
A time complexity of O(n^2).

This means that if the list size doubles, the time taken to sort it quadruples.

Question 13

What is the explanation of the time complexity for a merge sort?

Answer 13

Merge sort works by repeatedly halving the list into sub lists until there are n lists of 1 element.
The halving process takes O(log n) operations.
These sublists are then compared with adjacent sublists and ordered.
This takes O(n) operations.