1.2 Fundamental Algorithms

Question 1

Time Complexity of Linear Search and Binary Search.

Answer 1

Linear Search: O(n)
Binary Search: O(log n)

Question 2

State the average-case and worst-case time complexity of quicksort.

Answer 2

average-case : O(n log n)
worst-case : O(n^2)

Question 3

State the time complexity of bubble sort.

Answer 3

O(n^2)

Question 4

The implementation of the quicksort utilised the last data element of the array as the pivot.

Two programmmers carried out an experiment to test the execution time of two sorting algorithms using an array of sorted data containing 8 elements.

One of them used quicksort while the other used bubble sort. The one who used bubble sort discovered that his execution time was shorter as compared to the one who used quicksort.
Comment in this result.

Answer 4

Since the implementation of the quicksort utilised the last data element of the array as the pivot, this quicksort algorithm will have the worst-case time complexity of O(n^2) since the chosen pivot is the largest element.

Since bubble sort is used on a sorted array, it will have the best time complexity of O(n).

However, time efficiency only describes how execution time scales the amount of data and is not indicative of the execution time for small arrays such as 8 elements.

Question 5

Explain what a hash key is.

Answer 5

A hash key is used to generate a hash index in a hash table to search for or store a record.

Question 6

State the worst-case time complexity of a hash table search.

Answer 6

O(n)

Question 7

State 3 features of a good hashing algorithm.

Answer 7

1. uses all the input data
2. generates very different hash values for similar strings
3. uniformly distributes the data across the entire set of possible hash values