Given two different divide and conquer algorithms A and B having been designed to solve the problem P Algorithm A partitions P into 5 subproblems each of size n/ 3 .Here n is the input size for P It takes a total of Θ(n^2) time for the partition and combine steps (i.e. the overhead). While B partitions P into 10 subproblems each of size (n/4) And it takes a total of Θ(n^1.8) time for the partition and combine steps. Which of the two algorithms is preferable? Why?
No comments:
Post a Comment