Question

The selection algorithm generates two subproblems with size of n/5 and 7n/10, respectively. Is it possible to make the two subproblems have equal size and still run in a linear time? If it is possible, how to partition the numbers into groups? If it is not possible, justify

Answer 1

Solution: Yes, it is possible to divide a problem and solve it in linear time, for example, the list can be divided into two or more lists to search for a particular element within the list. This list can be further divided into a larger space until the element is not found. If the partition is carried out in such a way so that the list is divided into 2 partitions at each and every recursive call the total complexity of the solution is O(log₂n) which is a linear time complexity. That's how the binary search works, so if the list is divided into m partitions at each and every recursive call then the complexity of the solution is O(log_mn).

Here's the solution to your question, please provide it a 100% rating. Thanks for asking and happy learning!!