Algorithm UNIT Quiz

What is the time complexity of a linear search algorithm?

• O(n)

• O(log n)

• O(n log n)

• O(1)

Answer explanation

The time complexity of a linear search algorithm is O(n) because it may need to check each element in the list once in the worst case, where n is the number of elements. Thus, the correct choice is O(n).

Which asymptotic notation gives the upper bound of an algorithm's time complexity?

• Big-O

• Big-Ω

• Big-Θ

• None

Answer explanation

Big-O notation provides the upper bound of an algorithm's time complexity, indicating the worst-case scenario for its growth rate. It helps in understanding the maximum time an algorithm can take as input size increases.

What is the worst-case time complexity of a binary search algorithm?

• O(n)

• O(log n)

• O(n log n)

• O(1)

Answer explanation

The worst-case time complexity of a binary search algorithm is O(log n) because it repeatedly divides the search interval in half, leading to logarithmic growth relative to the number of elements.

Which algorithm has a time complexity of O(n^2)?

• Bubble sort

• Selection sort

• Insertion sort

• All of the above

Answer explanation

All the algorithms listed—Bubble sort, Selection sort, and Insertion sort—have a worst-case time complexity of O(n^2). Therefore, the correct answer is 'All of the above'.

What is the best-case time complexity of a heap sort algorithm?

• O(n)

• O(log n)

• O(n log n)

• O(1)

Answer explanation

The best-case time complexity of heap sort is O(n) during the heap construction phase. After that, the sorting phase takes O(n log n). However, the question specifically asks for the best-case scenario, which is O(n).

Which data structure is used in a heap sort algorithm?

• Array

• Linked list

• Stack

• Queue

Answer explanation

Heap sort uses an array to represent the binary heap structure. The array allows efficient access and manipulation of elements, making it suitable for the sorting process. Thus, the correct answer is Array.

What is the time complexity of a naive string-matching algorithm?

• O(n)

• O(n^2)

• O(n log n)

• O(1)

Answer explanation

The naive string-matching algorithm checks each position in the text for a match with the pattern. In the worst case, this results in O(n) comparisons for each of the n characters, leading to a total time complexity of O(n^2).

Which algorithm is used for finding a pattern in a text?

• Rabin-Karp algorithm

• Knuth-Morris-Pratt algorithm

• Naive string-matching algorithm

• All of the above

Answer explanation

All the listed algorithms—Rabin-Karp, Knuth-Morris-Pratt, and the Naive string-matching algorithm—are used for finding patterns in text. Therefore, the correct answer is 'All of the above'.

What is the time complexity of a binary search algorithm in the average case?

• O(n)

• O(log n)

• O(n log n)

• O(1)

Answer explanation

The binary search algorithm divides the search interval in half each time, leading to a logarithmic growth in the number of comparisons. Therefore, the average case time complexity is O(log n), making it efficient for sorted data.

Which asymptotic notation gives the lower bound of an algorithm's time complexity?

• Big-O

• Big-Ω

• Big-Θ

• None

Answer explanation

Big-Ω notation provides the lower bound of an algorithm's time complexity, indicating the minimum time required for an algorithm in the best-case scenario. It contrasts with Big-O, which gives an upper bound.