Time Complexity - Quiz

Binary search is an efficient search algorithm that operates on sorted arrays by repeatedly dividing the search interval in half. In each iteration, it compares the middle element with the target element and adjusts the search range accordingly. This process continues until the target element is found or the search range becomes empty. Since each comparison reduces the search space by half, the time complexity of binary search is logarithmic with respect to the number of elements in the array, denoted as O(log n).

Removing an element from a doubly linked list, given a reference to the node to be deleted, can be done in constant time. In a doubly linked

Merge sort is a divide-and-conquer sorting algorithm that recursively divides the array into smaller subarrays, sorts them individually, and then merges them back together. In each recursive call, the array is split in half, resulting in a logarithmic number of divisions. Afterward, the merging process takes linear time to combine the sorted subarrays. Therefore, the time complexity of merge sort in the worst case is O(n log n).

Selection sort is a simple comparison-based sorting algorithm that repeatedly selects the smallest element from the unsorted part of the array and swaps it with the element at the beginning of the unsorted part. In the worst case, for each pass of the algorithm, the smallest remaining element needs to be found by iterating through the unsorted part. This requires n-1 comparisons in the first pass, n-2 in the second pass, and so on, resulting in a quadratic time complexity of O(n^2).

In a linear search algorithm for finding the maximum element in an unsorted array, each element is checked sequentially to determine the maximum. In the worst case, the maximum element is located at the end of the array, requiring n comparisons. Therefore, the time complexity of the linear search for finding the maximum element is linear, denoted as O(n).

Binary search is a divide-and-conquer algorithm that repeatedly divides the search space in half. In each step, the middle element is compared with the target element, and the search space is reduced to either the left or right half. This process continues until the target element is found or the search space is empty. As binary search eliminates half of the search space in each step, the time complexity is logarithmic to the number of elements (n), denoted as O(log n).

Merge sort is a divide-and-conquer sorting algorithm that divides the array into smaller subarrays, recursively sorts them, and merges them to obtain the sorted array. In each recursion, the array is divided in half, resulting in a logarithmic number of levels. At each level, the merge operation combines two sorted subarrays, which takes linear time. Therefore, the time complexity of merge sort in the worst case is O(n log n).

In a breadth-first search (BFS) algorithm on a directed acyclic graph (DAG), each vertex is visited once, and each edge is traversed once. The time complexity of BFS on a DAG is proportional to the sum of the number of vertices (V) and the number of edges (E), denoted as O(V + E).

Bubble sort is a simple comparison-based sorting algorithm that repeatedly swaps adjacent elements if they are in the wrong order. In the worst case, where the array is reverse sorted, each pass of the algorithm requires traversing the entire array and potentially swapping adjacent elements. This results in a quadratic time complexity of O(n^2).

Topological sort is an algorithm used to linearly order the vertices of a directed acyclic graph (DAG) based on their dependencies. It employs depth-first search (DFS) to visit all the vertices, resulting in a time complexity proportional to the sum of the number of vertices (V) and the number of edges (E), denoted as O(V + E).