1. Algorithms X and Y take exactly T.(n) = cinlogn and Ty(n) = cn microseconds, respectively,...
Fantastic news! We've Found the answer you've been seeking!
Transcribed Image Text:
1. Algorithms X and Y take exactly T.(n) = cinlogn and Ty(n) = c₂n³ microseconds, respectively, for a problem of size n. Find the best algorithm for processing n = 220 data items if the algorithm X takes 10 microseconds to process 1024 items and the algorithm Y takes only 1 microsecond to process 1024 items? 2. If f(n) = n²/log n and g(n) = n(log n)², Explain (using algebraic expression) whether f(n) is in O(g(n)), 2(g(n), or 0(g(n)) ? 3. For the given code segment sum = 0; for(i=0;i<sqrt(n)/2;i++) sum++; for(j=0;j<sqrt(n)/4;j++) sum++; for(k 0;k<8+j;k++) sum++; (a) If it takes 0.5 ms for input size 100. How long will it take for input size 500 with respect to its running time (Big-Oh notation)? 4. Give an analysis of the running time (Big-Oh notation) for the following program fragments. Note that the running time corresponds here to the number of times each step is executed? (a) for(i=1;i<2*n;i++) for(j=1:j<i*i;j++) for(k=1;k<j;k++) if (j %i) sum++; (b) int count = 0; for (int i=n/2; i<n; i++) } for (int j=1; j<n; j = 2 *j) (c) int i=1, s=1; while (s <= n) { (d) i=n; for (int k=1; k<n; k = k * 2) count++; i++; s += i; while(i > 1) { while (j<n) { } i=i/2; k = 0; while (k <n) { } j<--j*2; k=k+ 2; } (e) Order the computed time complexities (a - d) by growth rate from slowest to fastest 1. Algorithms X and Y take exactly T.(n) = cinlogn and Ty(n) = c₂n³ microseconds, respectively, for a problem of size n. Find the best algorithm for processing n = 220 data items if the algorithm X takes 10 microseconds to process 1024 items and the algorithm Y takes only 1 microsecond to process 1024 items? 2. If f(n) = n²/log n and g(n) = n(log n)², Explain (using algebraic expression) whether f(n) is in O(g(n)), 2(g(n), or 0(g(n)) ? 3. For the given code segment sum = 0; for(i=0;i<sqrt(n)/2;i++) sum++; for(j=0;j<sqrt(n)/4;j++) sum++; for(k 0;k<8+j;k++) sum++; (a) If it takes 0.5 ms for input size 100. How long will it take for input size 500 with respect to its running time (Big-Oh notation)? 4. Give an analysis of the running time (Big-Oh notation) for the following program fragments. Note that the running time corresponds here to the number of times each step is executed? (a) for(i=1;i<2*n;i++) for(j=1:j<i*i;j++) for(k=1;k<j;k++) if (j %i) sum++; (b) int count = 0; for (int i=n/2; i<n; i++) } for (int j=1; j<n; j = 2 *j) (c) int i=1, s=1; while (s <= n) { (d) i=n; for (int k=1; k<n; k = k * 2) count++; i++; s += i; while(i > 1) { while (j<n) { } i=i/2; k = 0; while (k <n) { } j<--j*2; k=k+ 2; } (e) Order the computed time complexities (a - d) by growth rate from slowest to fastest
Expert Answer:
Answer rating: 100% (QA)
1 It is given that Tx C n log n microseconds We hav... View the full answer
Related Book For
Modeling the Dynamics of Life Calculus and Probability for Life Scientists
ISBN: 978-0840064189
3rd edition
Authors: Frederick R. Adler
Posted Date:
Students also viewed these general management questions
-
X and Y take the value 0 with probability 0.5 and the value 1 with probability 0.5. Consider independent random variables X and Y with identical probability distributions as given. Let Z = X + X and...
-
X and Y take the value 0 with probability 0.25, the value 1 with probability 0.5, and the value 2 with probability 0.25. Consider independent random variables X and Y with identical probability...
-
When does the cost of goods sold move from the balance sheet to the income statement? A) When goods are put into production. B) While in finished goods inventory. C) After the products are finished....
-
For each of the transactions for Cone Corporation in Exercise 15, indicate the amount of the increase or decrease on the appropriate element of the balance sheet or income statement. The first...
-
What is a codebook and what is it used for?
-
Suppose you are considering buying shares in IMT, Inc. IMT's next yearly dividend is expected to be $1.50 per share, and all subsequent dividends are expected to shrink by 10 percent per year for the...
-
Transaction data For Crofoot Real Estate Agency are presented in E3-7. Instructions Journalize the transactions. Do not provide explanations. From E3-7 Oct. 1 Stockholders invest $30,000 in exchange...
-
Please calculate and provide answers to the following problems Compute the sales mix percentages for the following: Rooms Sales: $60,000.00/ Food Sales: $15,000.00/ Beverage Sales: $10,000 Compute...
-
The proposed rates were not in the range the CEO expected given the pricing analysis. The CEO has asked the pricing actuary to verify the total projected loss cost excluding potential large storm...
-
W6: Construct arguments related to logistical problems by writing supportive argumentative essays Explain the importance of constructing a logical position or argument for research. Do you feel that...
-
True or False. The principle of conservation of energy can be used to derive the equation of motion of both damped and undamped systems.
-
What effect does a decrease in the stiffness of the system have on the natural period?
-
True or False. When a mass vibrates in a vertical direction, its weight can always be ignored in deriving the equation of motion.
-
True or False. The natural frequency of vibration of a torsional system is given by \(\sqrt{\frac{k}{m}}\), where \(k\) and \(m\) denote the torsional spring constant and the polar mass moment of...
-
What effect does a decrease in mass have on the frequency of a system?
-
Make or Buy A company manufactures various-sized plastic bottles for its medicinal product. The manufacturing cost for small bottles is $160 per unit (100 bottles), including fixed costs of $33 per...
-
Why did management adopt the new plan even though it provides a smaller expected number of exposures than the original plan recommended by the original linear programming model?
-
Student 2 comes to class with probability 8/9 if student 1 does. Student 3 ignores them. A small class has only three students. Each comes to class with probability 0.9. Find the probability that all...
-
Use Newton's method for three steps to solve the following equations. Find and sketch the tangent line for the first step, then find the Newton's method discrete-time dynamical system to check your...
-
Redo the test using . How different are the results? Under what circumstances might it make a larger difference which proportion was used? Algorithm 8.4 uses 1 and 2 to estimate the variance under...
-
What is the drawback of company rankings based on EVA?
-
If EPS rises after a deal, does this necessarily imply value creation?
-
Can value be created by developing new products and new markets or by reducing costs?
Study smarter with the SolutionInn App