Time Complexity

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

Inserting an element at the beginning of a dynamic array requires shifting all existing elements one position to the right to make room for the new element. Since the number of elements in the array affects the number of shifts required, the time complexity of this operation is linear, denoted as O(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).

In a linear search algorithm, each element of the array is checked one by one until the target element is found or the end of the array is reached. In the worst case, where the target element is at the last position or absent from the array, the algorithm will need to examine all n elements. Therefore, the time complexity of a linear search is linear, denoted as O(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

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

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

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

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 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 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 breadth-first search (BFS) 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 BFS on a tree is proportional to the number of nodes, denoted as O(N).

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

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

In a balanced binary search tree, such as an AVL tree or a red-black tree, the average-case search operation is efficient. The tree's balanced structure ensures that the height remains logarithmic to the number of elements (n), resulting in a time complexity of O(log n) for search operations.

In the worst case, a hash table's insertion operation may require rehashing or resizing the underlying array, which involves copying elements. As a result, the worst-case time complexity of an insertion operation in a hash table is linear to the number of elements (n), 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 binary heap, the delete operation removes the root element, which is typically the minimum or maximum element depending on the heap's type. After removing the root, the heap needs to restore the heap property by percolating down or up, which involves swapping elements and comparing them with their children or parent. As the height of a binary heap is logarithmic to the number of elements (n), the worst-case time complexity of a delete operation is O(log n).

Quicksort is a comparison-based sorting algorithm that divides the array into two subarrays based on a pivot element, recursively sorts the subarrays, and combines them. In the worst case, if the pivot selection consistently results in unbalanced partitions, quicksort degrades to its quadratic time complexity. This occurs when the pivot is always the minimum or maximum element, leading to n recursive calls and resulting in a time complexity of O(n^2).

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

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

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

Selection sort is an in-place comparison-based sorting algorithm that repeatedly selects the minimum or maximum element and places it in the sorted portion of the array. In the worst case, selection sort requires nested iterations, comparing each element with the remaining unsorted portion. This results in a quadratic time complexity of O(n^2).