Time Complexity - Quiz

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

Bubble sort is a simple comparison-based sorting algorithm that repeatedly steps through the array, compares adjacent elements, and swaps them if they are in the wrong order. In the worst case, where the array is sorted in reverse order, each pass of the algorithm will result in the largest unsorted element "bubbling" to the end of the array. 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).

Breadth-first search (BFS) is a graph traversal algorithm that explores all vertices at the same level before moving to the next level. In the worst case, BFS visits each vertex once and each edge once, resulting in a time complexity proportional to the sum of the number of vertices (V) and the number of edges (E). Hence, the time complexity of BFS is O(V + E).

Binary heaps are a type of complete binary tree used to implement priority queues. In the worst case, when inserting an element into a binary heap, it needs to compare the element with the parent node and potentially swap them to maintain the heap property. As the height of a binary heap is logarithmic to the number of elements (n), the worst-case insertion operation has a time complexity of O(log n).

Depth-first search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. In the worst case, DFS visits each vertex once and each edge once, resulting in a time complexity proportional to the sum of the number of vertices (V) and the number of edges (E). Therefore, the time complexity of DFS is O(V + E).

In a stack implemented using a singly linked list, the pop operation removes the top element from the stack. Since the linked list maintains a reference to the top node, the pop operation can be performed in constant time by updating the reference to the next node. Thus, the time complexity of the pop operation is O(1).

In a depth-first search (DFS) algorithm on a tree, each node is visited exactly once, and each edge is traversed once. As a tree has N-1 edges for N nodes, the time complexity of DFS on a tree is proportional to the number of nodes, denoted as O(N).

Radix sort is a non-comparative sorting algorithm that sorts elements by their individual digits or bits. In the worst case, where the number of digits (k) is constant, radix sort performs counting sort or bucket sort on each digit. Since each counting sort or bucket sort takes linear time (O(n)), and there are k digits to sort, the overall time complexity becomes O(nk).

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).

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).