Suppose you are choosing between the following three algorithms to solve a problem: Algorithm A solves...

 

Transcribed Image Text:

Suppose you are choosing between the following three algorithms to solve a problem: Algorithm A solves the problem of size n by dividing them into five subproblems of size n/2. conquer the subproblems by solving them recursively. Base case is reached when the input size is less than or equal to 1. Each subproblem combines the solutions in time linear to the subproblem input size. Algorithm B solves the problem of size n by dividing them into two subproblems of size n - 1, conquer the subproblems by solving them recursively. Base case is reached when the input size is less than or equal to 1. Each subproblem combines the solutions in constant time. Algorithm C solves the problem of size n by dividing them into nine subproblems of size n/3, conquer the subproblems by solving them recursively. Base case is reached when the input size is less than or equal to 1. Each subproblem combines the solutions in time square to the subproblem input size. (a) Write down the recurrence equation and give the tightest asymptotic upper bound (big-O) of each of these algorithms. (b) Which algorithm is the fastest? Suppose you are choosing between the following three algorithms to solve a problem: Algorithm A solves the problem of size n by dividing them into five subproblems of size n/2. conquer the subproblems by solving them recursively. Base case is reached when the input size is less than or equal to 1. Each subproblem combines the solutions in time linear to the subproblem input size. Algorithm B solves the problem of size n by dividing them into two subproblems of size n - 1, conquer the subproblems by solving them recursively. Base case is reached when the input size is less than or equal to 1. Each subproblem combines the solutions in constant time. Algorithm C solves the problem of size n by dividing them into nine subproblems of size n/3, conquer the subproblems by solving them recursively. Base case is reached when the input size is less than or equal to 1. Each subproblem combines the solutions in time square to the subproblem input size. (a) Write down the recurrence equation and give the tightest asymptotic upper bound (big-O) of each of these algorithms. (b) Which algorithm is the fastest?

Answer rating: 100% (QA)

a The recurrence equations and the tightest asymptotic upper bounds ... View the full answer