Computer Science: Algorithms

What does Big O notation represent in the context of algorithm analysis?

Big O notation describes the upper bound of an algorithm's growth rate, characterizing the worst-case execution time or space requirements as the input size (n) approaches infinity.

What is the worst-case time complexity of the Bubble Sort algorithm?

O(n^2), where n is the number of elements in the input list, due to the nested loops required to compare and swap elements.

What is the auxiliary space complexity of a standard Merge Sort implementation?

O(n), because the algorithm requires a temporary array of the same size as the input to merge the divided sub-arrays.

What is the primary pre-condition for an input array before performing a Binary Search?

The input array must be sorted in either ascending or descending order for the divide-and-conquer logic to function correctly.

Which data structure is typically used to implement Breadth-First Search (BFS)?

A Queue (FIFO - First In, First Out) is used to keep track of the nodes to be visited in the order they were discovered.

What are the two essential components required for a valid recursive function?

A base case (to terminate the recursion) and a recursive step (which calls the function again with a smaller input to move toward the base case).

Between O(n log n) and O(n^2), which complexity is more efficient for large input sizes, and why?

O(n log n) is more efficient because its growth rate is significantly slower than the quadratic growth of O(n^2) as the input size n increases.

Why is Quick Sort often preferred over Merge Sort in practice, despite Quick Sort's O(n^2) worst-case time complexity?

Quick Sort is an in-place algorithm (requiring only O(log n) auxiliary space) and typically exhibits better cache locality and smaller constant factors than Merge Sort.

What does it mean for a sorting algorithm to be 'stable'?

A sorting algorithm is stable if it preserves the relative order of records with equal keys (values) from the original input.

What is the time complexity of Binary Search, and why?

O(log n), because the algorithm halves the search space in every iteration, leading to a logarithmic number of steps relative to the input size.