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....
-
The energy we require to live comes from the chemically stored potential energy in food, which is transformed into other energy forms during the metabolism process. What happens to a person whose...
-
Leonard and Linda Lindsay sold for $350,000 in October 2019 their residence that they had purchased in 2009 for $100,000. They made major capital improvements during their 10-year ownership totaling...
-
Go through each of the arguments for restricting trade and provide a counter-argument for not restricting trade.
-
Wins Companies, a home improvement store chain, reported the following summarized figures: Requirements 1. Compute Wins Companies current ratio at May 31, 2012 and 2011. 2. Did Wins Companies current...
-
The partnership agreement of Archie and Jughead has the following provisions: The partners are to earn 10 percent on the average capital. Archie and Jughead are to earn salaries of $20,000 and...
-
Indicate whether the statement is true or false, and justify your answer. Unlike with most types of goods, deriving a demand curve for health care is quite simple because people rarely skimp on...
-
Using the ABC analysis, determine new segment profitability statements. Based on your analysis in questions 1 and 2, what changes would you suggest to General Mills? What recommendations do you...
-
Develop an assembly language version for the ARM ISA for the following C code (10 pts) int a[100]; for (i=0;i <100%;i++) { a[i] = 100-1; }
-
What is the total rate of return for an investor who buys a 3 - year bond with an annual coupon of 6 . 5 % and annual market rate of 5 . 5 % , then sells the bond 6 months later for $ 1 , 0 3 7 . 1 9...
-
1 . Consider a firm that has 3 2 % of debt, 9 % of preferred stock, and 5 9 % of equity. The rates of return for debt, preferred stock, and equity are 4 % , 9 % , and 1 4 % , respectively. The...
-
What is the future value of $ 4 0 0 invested as a lump sum today in 8 years if the annual stated rate of interest is 1 2 % and is compounded monthly?
-
The project has a $ 4 8 , 3 0 0 initial outlay, cash inflows of $ 1 7 , 5 8 0 per year for 5 years, and an interest rate of 1 5 % . What is the project's Profitability Index ( PI ) ? Should this...
-
The 1 9 6 8 Mexico City Olympics is largely remembered for what?
-
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...
-
Suppose your firm could purchase another firm for only half of its replacement value. Would that be a sufficient justification for the acquisition? Why or why not?
-
What major merger waves have occurred in the United States?
-
What are the two questions that an acquirer must answer?
Study smarter with the SolutionInn App