- A O(n)
- B O(1)
- C O(log n)
- D O(n log n)
When appending an element to the end of a dynamic array with sufficient capacity, the operation can be performed in constant time. This is because the dynamic array allocates extra space to accommodate additional elements, and appending a new element simply requires placing it at the next available index. The time complexity of this operation is constant, denoted as O(1).
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).
Hash tables use a hash function to map keys to array indices, allowing constant-time access to elements. In the average case, the hash function distributes the keys evenly, resulting in a constant number of probes to find the desired element. As a result, the time complexity of a search operation in a hash table is O(1).
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).
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 an array, the push operation inserts an element at the top of the stack. Since the top position is known, the push operation can be performed in constant time by simply incrementing the top index and storing the element in the corresponding array position. Therefore, the time complexity of the push 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).
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).
In a depth-first search (DFS) algorithm on a directed acyclic graph (DAG), each vertex is visited once, and each edge is traversed once. The time complexity of DFS 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).
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).