Algorithm Complexity Quiz

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

• $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 time complexity. In the worst-case scenario, it takes O(log n) time to find the target or determine its absence.

Which of the following best describes the time complexity of the bubble sort algorithm in the average case?

• $O(n)$

• $O(n \log n)$

• $O(n^2)$

• $O(\log n)$

Answer explanation

The average case time complexity of bubble sort is $O(n^2)$ because it involves nested loops, where each element is compared to every other element, leading to quadratic growth in the number of comparisons as the input size increases.

What is the space complexity of the merge sort algorithm?

• $O(1)$

• $O(\log n)$

• $O(n)$

• $O(n^2)$

Answer explanation

The space complexity of merge sort is $O(n)$ because it requires additional space for the temporary arrays used during the merging process. This is necessary to hold the elements being merged, making $O(n)$ the correct choice.

Which of the following algorithms has a time complexity of $O(n \log n)$ in the best, average, and worst cases?

• Quick Sort

• Merge Sort

• Bubble Sort

• Insertion Sort

Answer explanation

Merge Sort consistently has a time complexity of O(n log n) in the best, average, and worst cases due to its divide-and-conquer approach. In contrast, Quick Sort can degrade to O(n^2) in the worst case, while Bubble and Insertion Sort are O(n^2) in average and worst cases.

What is the time complexity of finding the maximum element in an unsorted array?

• $O(1)$

• $O(\log n)$

• $O(n)$

• $O(n^2)$

Answer explanation

To find the maximum element in an unsorted array, you must examine each element at least once. This results in a time complexity of O(n), where n is the number of elements in the array.

Which of the following data structures has a time complexity of $O(1)$ for both insertion and deletion operations?

• Stack

• Queue

• Linked List

• Hash Table

Answer explanation

A Hash Table allows for average-case O(1) time complexity for both insertion and deletion due to its use of a hash function to access elements directly. In contrast, Stacks, Queues, and Linked Lists have varying complexities.

What is the time complexity of the depth-first search (DFS) algorithm in a graph with $V$ vertices and $E$ edges?

• $O(V + E)$

• $O(V^2)$

• $O(E \log V)$

• $O(V \log V)$

Answer explanation

The time complexity of DFS is $O(V + E)$ because it visits each vertex once and explores each edge once. This accounts for all vertices and edges in the graph, making $O(V + E)$ the correct choice.

Which of the following algorithms is not comparison-based?

• Quick Sort

• Merge Sort

• Counting Sort

• Heap Sort

Answer explanation

Counting Sort is not comparison-based; it sorts integers by counting occurrences, while Quick Sort, Merge Sort, and Heap Sort rely on comparisons to order elements.

What is the time complexity of inserting an element into a binary search tree (BST) in the average case?

• $O(1)$

• $O(\log n)$

• $O(n)$

• $O(n \log n)$

Answer explanation

In a binary search tree, the average case for insertion occurs when the tree is balanced. This results in a height of log(n), leading to an average time complexity of O(log n) for inserting an element.

Which of the following best describes the time complexity of the Floyd-Warshall algorithm for finding shortest paths in a graph?

• $O(V^2)$

• $O(V^3)$

• $O(VE)$

• $O(E \log V)$

Answer explanation

The Floyd-Warshall algorithm has a time complexity of O(V^3) because it uses three nested loops to iterate over all pairs of vertices, making it efficient for dense graphs with V vertices.