Computers and Technology, 17.08.2021 02:50 srshelton

Suppose you are choosing between the following three algorithms: 1) Algorithm A solves problems by dividing them into five subproblems of half the size, recursively solving each subproblem, and then combining the solutions in linear time.
2) Algorithm B solves problems of size n by recursively solving two subproblems of size n - 1 and then combining the solutions in constant time.
3) Algorithm C solves problems of size n by dividing them into nine subproblems of size n/3, recursively solving each subproblem, and then combining the solutions in O(n^2) time.
What are the running times of each of these algorithms (in big-O notation), and which would you choose?
a) This is a case of the Master theorem with a = 5, b = 2, d = 1. As a > b^d, the running time is O(n^logb a) = O(n^log2 5) = O(n^2.33).
b) T(n) = 2T(n−1)+C, for some constant C. T(n) can then be expanded to C * the summation from i = 0 to n−1 2^i+2^n * T(0) = O(2^n).
c) This is a case of the Master theorem with a = 9, b = 3, d = 2. As a = b^d, the running time is O(n^d log n) = O(n^2 log n).

Answers: 1

Show answers

Another question on Computers and Technology

Computers and Technology, 22.06.2019 16:00

You have inserted new slides based on a word outline. how do you format these new slides to match the powerpoint presentation formatting? a. select all slides in the presentation and click format on the home tab. b. select the new slides and click reset on the home tab. c. select all slides in the presentation and click reset on the home tab. d. select the new slides and click format on the home tab.

Answers: 3

Answer

Computers and Technology, 22.06.2019 17:20

[a] create a class called “cycle” which has two instance integer variables as properties, “numberofwheels” and “weight.” create a constructor with two parameters, using the same variable names in the parameter list. assign each variable to numberofwheels” and “weight” respectively. write a separate application to test the class and display its properties. note: do not change the names of the instance variables or the variables listed in the constructor’s parameter list. [b] edit your class cycle by adding a default constructor which will assign the default values of 100 to represent the numberofwheels, and 1000 to represent the weight, by invoking a call to the other constructor. modify your application created in [a] to test the class.

Answers: 3

Answer

Computers and Technology, 22.06.2019 18:00

What is the first view you place in your drawing?

Answers: 1

Answer

Computers and Technology, 22.06.2019 19:30

Once the data center routes to the destination server that hosts the website, what's the next step in the internet process? user’s browser renders html code from destination server into web page request goes through router/model and isp request routed to nameserver and datacenter

Answers: 2

Answer

You know the right answer?

Suppose you are choosing between the following three algorithms: 1) Algorithm A solves problems by...

Questions