Arrange the following time complexities in increasing order. $$ (A) \text{ Bubble sort (worst case) } $$ $$ \text{ (B). Deleting head node in singly linked list } $$ $$ \text{ (C). Binary search } $$ $$ \text{ (D). Worst case of merge sort } $$
Step-by-step Solution:
Arrange the following operations and algorithms by their time complexities in increasing order (fastest to slowest).
Let's determine the time complexity for each item, assuming an input size of 'n'.
To delete the head node, you only need to change the head pointer to point to the next node (head = head.next). This is a single, direct operation that doesn't depend on the number of elements in the list.
Time Complexity: \(O(1)\) (Constant)
Binary search operates on a sorted array by repeatedly dividing the search interval in half. This "halving" approach means the number of operations grows logarithmically with the input size 'n'.
Time Complexity: \(O(\log n)\) (Logarithmic)
Merge sort is a "divide and conquer" algorithm. It recursively divides the list into halves until it has 'n' sublists of one element. This division process creates a recursion tree of height \(\log n\). At each level of the tree, all elements are merged, which takes \(O(n)\) time. The total time is the work per level times the number of levels.
Time Complexity: \(O(n \log n)\) (Linearithmic)
In its worst-case scenario (e.g., a reverse-sorted list), Bubble Sort must iterate through the list approximately 'n' times. For each of these iterations, it performs another inner iteration that also takes up to 'n' steps. This nested loop structure results in a quadratic growth rate.
Time Complexity: \(O(n^2)\) (Quadratic)
Now, we arrange these complexities in increasing order of their growth rate, from fastest to slowest:
$$O(1) < O(\log n) < O(n \log n) < O(n^2)$$
Mapping this back to our original items, we get the final sequence: