DBMS

Selection sort makes n-1 passes, each time scanning remaining unsorted elements to find the minimum. This always requires roughly n²/2 comparisons, giving O(n²) in all cases.

Insertion sort's average case involves shifting roughly half the sorted portion on average per insertion, leading to O(n²) comparisons and shifts overall.

Insertion sort's worst case occurs with reverse-sorted input, where each new element must shift through all existing sorted elements, requiring O(n²) comparisons and shifts.

Bubble sort's worst case occurs with reverse-sorted input, requiring maximum passes (n-1) and maximum comparisons/swaps per pass, resulting in O(n²) total operations.

Quick sort's average case achieves O(n log n) when pivots consistently create roughly balanced partitions, dividing the problem size logarithmically.

Merge sort requires O(n) auxiliary space for the temporary arrays used during the merge phase of each recursive call, regardless of time complexity.

Merge sort always divides input in half and recursively merges, requiring n comparisons per level across log n levels, giving O(n log n) in all cases.

Quick sort's worst-case space complexity is O(n) for recursive implementations when poor pivots create maximum recursion depth, causing stack frames proportional to input size. (Note: optimized implementations using tail recursion or iteration can achieve O(log n)).

Quick sort's worst case occurs when pivots consistently create maximally unbalanced partitions (sorted or reverse-sorted input with poor pivot choice), degrading to O(n²) time complexity.

Selection sort always performs n-1 passes with decreasing comparisons per pass, totaling approximately n²/2 comparisons regardless of input order, giving O(n²) in all cases.

Merge sort requires O(n) auxiliary space in the worst case because it needs to merge subarrays by copying elements into temporary arrays. The divide-and-conquer approach creates new arrays during the merge phase.

Quick sort uses the divide and conquer paradigm by selecting a pivot element and partitioning the array around it. It then recursively sorts the sub-arrays on either side of the pivot.

A circular doubly linked list allows O(1) concatenation because you only need to update a few pointers: connect the tail of the first list to the head of the second, and vice versa. This works in constant time regardless of list size.

The Floyd-Warshall algorithm for all pairs shortest path uses dynamic programming. It builds solutions incrementally by considering intermediate vertices, storing results in a 2D table to avoid redundant calculations.

Depth-first search (DFS) can find connected components by traversing all reachable vertices from a starting point. Each DFS call identifies one connected component; repeat DFS from unvisited vertices to find all components.

Minimum spanning tree algorithms like Prim's and Kruskal's use the greedy approach. They make locally optimal choices at each step (selecting the minimum weight edge that doesn't create a cycle) which leads to a globally optimal solution.

Merge sort consistently performs at O(nlogn) time complexity in all cases - best, average, and worst. The algorithm divides the array log n times and merges n elements at each level, giving nlog n total operations.

Bubble sort has O(n²) average time complexity because in the average case, it requires multiple passes through the array. For n elements, it makes approximately n²/2 comparisons and swaps in the average scenario.