Answer Happy

Divide and Conquer 1 Suppose you have to choose among three algorithms to solve a problem: Algorithm A solves an instance of size n by recursively solving 4 instances of size, and then combining their solutions in time O(n3) Algorithm B solves an instance of size n by recursively solving 8 instances of size, and then combining their solutions in time O(n?) Algorithm C solves an instance of size n by recursively solving n instances of size, and then combining their solutions in time O(n). Algorithm D solves an instance of size n by recursively solving two instances of size 2n, and then combining their solutions in time O(log n). Which one of these algorithms would you prefer? Which one is the worst? Why? (Hint: Compute time complexity (big-o) of all algorithms.) n