Question
1) Let A and B be two programs that perform the same task. Let tA (n)...
1) Let A and B be two programs that perform the same task. Let tA (n) and tB (n), respectively, denote their run times. For each of the following pairs, find the range of n values for which program A is faster than program B. Show the values for each and how you obtained them (justify).
a) tA (n) =1000n , tB (n) =10n^2
b) tA (n) = 2n^2 , tB (n) = n ^3
c) tA (n) = 2^n , tB (n) =100n
d) tA (n) =1000n logn , tB (n) = n^2
Answers
The best way of calculating this is by using an Excel sheet or a programming language with a looping construct. For the first column in excel I am putting value of n. Next column as tA(n), next as tB(n) and last column as tA(n)-tB(n). When the value of 4th column is negative it is when tA(n) is faster as compared to tB(n). The thing with excel is you can easily expand using the small dot at the bottom right of the cell. With a programming language you just need to add an if statement to find a starting point and by looking at functions you can detemined if there will be an ending point or not (if tA(n) is asymptotically smaller as compared to tB(n) then there will be no ending point).
a. n = 101 to infinity
b. n = 3 to infinity
c. n = 0 to 9
d. n = 3551 to infinity
Similar Solved Questions
5 answers
An optical fiber made of glass with an index of refraction 1.50
An optical fiber made of glass with an index of refraction 1.50 that is coated with a material with index of refraction 1.30 has a critical angle ofA. 41.8°B. 60.0°C. 50.2°D. 90VE. This combination will not work...
1 answers
4. Suppose Yi Y, are id randonn variables with E(Y )-μ, Var(Y)= σ2 < o For...
4. Suppose Yi Y, are id randonn variables with E(Y )-μ, Var(Y)= σ2 < o For large n, find the approximaate distribution of YBeure to name any theorems you used....
1 answers
Chapter 2 Homework Set G 6 Moody Corporation uses a job-order costing system with a plantwide...
Chapter 2 Homework Set G 6 Moody Corporation uses a job-order costing system with a plantwide predetermined overhead rate based on machine-hours beginning of the year, the company made the following estimates: 10 Machine-hours required to support estinated production Fixed manufacturing overhead cos...
1 answers
Assume that the market demand and supply curves for milk are as shown in the graph...
Assume that the market demand and supply curves for milk are as shown in the graph below. As shown in the graph, the market clearing price is $3 per gallon and the quantity exchanged is 100 gallons per hour. Now assume that the government imposes a tax of 2$ per gallon of milk produced. a. What is ...
1 answers
Kandon Enterprises, Inc., has two operating divisions; one manufactures machinery and the other breeds and sells...
Kandon Enterprises, Inc., has two operating divisions; one manufactures machinery and the other breeds and sells horses. Both divisions are considered separate components as defined by generally accepted accounting principles. The horse division has been unprofitable, and, on November 15, 2021, Kand...
1 answers
Positive cooperativity is when binding of a ligand to a protein results in a conformational change...
Positive cooperativity is when binding of a ligand to a protein results in a conformational change that allows increased binding affinity at other ligand binding sites in the same molecule. Select one: True False...
1 answers
At one store, 33.4% of the 600 customers surveyed said checkout lines are too long. Find...
At one store, 33.4% of the 600 customers surveyed said checkout lines are too long. Find the margin of error for 95% confidence for the proportion of customers that said checkout lines are too long....
1 answers
A bar magnet is moved (in the plane of the page) with respect to a single-tur...
A bar magnet is moved (in the plane of the page) with respect to a single-tur of radius 5.00 cm as shown (the coil lies in a plane perpendicular to the di of the bar magnet). Over a time interval of 0.150 s, the magnitude of the magnetic field at the coil varies from 0.640 T to 0.240 T. The resistan...
1 answers
Sam's Sushi serves only a fixed-price lunch. The price of $10 and the variable cost of...
Sam's Sushi serves only a fixed-price lunch. The price of $10 and the variable cost of $5 per meal remain constant regardless of volume. Sam can increase lunch volume by opening and staffing additional check-out lanes. Sam has three choices, as follows. 1 Lane 2 Lanes 3 Lanes Monthly Volume Rang...
1 answers
The U-238 nucleus emits a 4.2MeV alpha particle . what is the total energy released in this decay
the U-238 nucleus emits a 4.2MeV alpha particle . what is the total energy released in this decay...
1 answers
Calculate the solubility at 25 °C of AgCl in pure water and in a 0.0140 M...
Calculate the solubility at 25 °C of AgCl in pure water and in a 0.0140 M AgNO3 solution. You'll find K, data in the ALEKS Data tab. Round both of your answers to 2 significant digits. solubility in pure water: نامه نامه solubility in 0.0140 M ...
1 answers
Hint: H3. Let W1 = {ax? + bx² + 25x + a : a, b e...
hint: H3. Let W1 = {ax? + bx² + 25x + a : a, b e R}. (a) Prove that W is a subspace of P3(R). (b) Find a basis for W. (c) Find all pairs (a,b) of real numbers for which the subspace W2 = Span {x} + ax + 1, 3x + 1, x + x} satisfies dim(W. + W2) = 3 and dim(Win W2) = 1. H3. (a) Use Theorem 1.8.1...
1 answers
According to the Nutrition Facts panel on a food package, a serving of the product provides 25%DV for sodium....
According to the Nutrition Facts panel on a food package, a serving of the product provides 25%DV for sodium. The DV for sodium is 2300 mg. Each serving of this product provides approximately _mg of sodium Multiple Choice Ο 575 Ο Ο More information is needed to estimate the a...
1 answers
Question 1 4.5 pts Given are five observations for two variables, x and y. 3 2...
Question 1 4.5 pts Given are five observations for two variables, x and y. 3 2 7 h. Compute the mean square error (MSE) O 3.875 4.133 4.421 4.312 i. Compute the standard error of the estimate 2.326 1.895 2.033 2.213 j. Compute the estimated standard deviation (standard error) of bu 0.643 0.697 0.568...