Do a complexity analysis on each of the loops below and determine its complexity class. Confirm...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Do a complexity analysis on each of the loops below and determine its complexity class. Confirm your results using empirical analysis where necessary. (1) Sum = 0; for(i=0; i < N; i++ ) (2) Sum = 0; Sum++; for(i=0; i < N; i++) for(j = 0; j < N; j++) (3) Sum = 0; Sum++; for(i=0; i < N; i++ ) for(j=0; j < N * N; j++) Sum++; (4) Sum = 0; for(i=0; i < N; i++ ) for( j = 0; j < 1; j++) Sum++; (5) Sum = 0; for(i=0; i < N; i++ ) for(j = 0; j < i * i; j++) for(k = 0; k < j; k++ ) Sum++; (6) Sum = 0; for(i = 1; i < N; i++ ) for(j=1; j < i * i; j++) if( j % i == 0) for(k = 0; k < j; k++ ) Sum++; Turn in a written report showing the analysis of each algorithm and, where necessary, a table of results for various values of N (at least five) showing the correctness of your analysis. The report should be no more than one page in length. Example: Do a complexity analysis on each of the loops below and determine its complexity class. Confirm your results using empirical analysis where necessary. (1) Sum = 0; for(i=0; i < N; i++ ) (2) Sum = 0; Sum++; for(i=0; i < N; i++) for(j = 0; j < N; j++) (3) Sum = 0; Sum++; for(i=0; i < N; i++ ) for(j=0; j < N * N; j++) Sum++; (4) Sum = 0; for(i=0; i < N; i++ ) for( j = 0; j < 1; j++) Sum++; (5) Sum = 0; for(i=0; i < N; i++ ) for(j = 0; j < i * i; j++) for(k = 0; k < j; k++ ) Sum++; (6) Sum = 0; for(i = 1; i < N; i++ ) for(j=1; j < i * i; j++) if( j % i == 0) for(k = 0; k < j; k++ ) Sum++; Turn in a written report showing the analysis of each algorithm and, where necessary, a table of results for various values of N (at least five) showing the correctness of your analysis. The report should be no more than one page in length. Example:
Expert Answer:
Related Book For
Applied Regression Analysis and Other Multivariable Methods
ISBN: 978-1285051086
5th edition
Authors: David G. Kleinbaum, Lawrence L. Kupper, Azhar Nizam, Eli S. Rosenberg
Posted Date:
Students also viewed these programming questions
-
I need assistance with the question "The Case of the 1901 Pharmacy Chain in Egypt for Marketing Management." . Please give all possible reasons for the collapse of the 19011 chain of pharmacies /...
-
"internet radios" for streaming audio, and personal video recorders and players. Describe design and evaluation processes that could be used by a start-up company to improve the usability of such...
-
Jake Drewrey has total fixed monthly expenses of $ 1,340 and his gross monthly income is $3,875. What is his debt-to-income ratio? How does his ratio compare to the desired ratio?
-
The general design recommendations for a well in sand casting are that (a) Its diameter should be twice the sprue exit diameter, and (b) The depth should be approximately twice the depth of the...
-
A manager of a large corporation recommends a $10,000 raise be given to keep a valued subordinate from moving to another company. What internal and external sources of data might be used to decide...
-
Quilts R Us (QRU) is considering investing in a new patterning attachment with the cash flow profile shown in the table below. QRU's MARR is 13.5 percent/year. a. What is the internal rate of return...
-
A comparative balance sheet for Shabbona Corporation is presented below. Additional information: 1. Net income for 2014 was $125,000. No gains or losses were recorded in 2014. 2. Cash dividends of...
-
6. A carver begins work on a block of granite that measures 20 cm by 10 cm by 5 cm. Granite has a density of 2.7 g/cm. What is the mass of the piece of granite? a. What do you need to calculate...
-
Preparing the Olney Company's Employee Payroll Register for the pay period ending January 8th, 20--. In previous chapters, gross wages were computed for each employee and using this data, FICA...
-
A very rare disorder is shown to depend on the genotype at three unlinked autosomal loci, A/a, B/b and C/c and that to be affected one must be homozygous for the rare allele at all three loci, that...
-
A producer task is known to be able to process data at a rate that is exponentially distributed with average service time of 3 ms per datum. What is the maximum allowable average data rate if the...
-
Grove Hotel hired Fortas, an electrical contractor, and paid him with a promissory note for $3,400. The note stated that it was with interest at prevailing bank rates. Did the stipulation about...
-
A producer generates data at 1 byte per 200 ns in bursts of 64 K bytes. A consumer, on the other hand, can read the data in 32 - bit words, but only at a rate of 1 word every 2s. Calculate the...
-
Higgins was a used-car dealer. He purchased a Corvette, giving the seller a draft drawn by him on the First State Bank of Albertville in the amount of $8,115. This draft was later presented by the...
-
Recalculate the FP (function point) metric for the inertial measurement system using a set of weightings that assumes that significant off - the - shelf software (say 70%) is to be used. Make...
-
Select an organization Facebook and write a paper in which you need to address the follwoign: Is profiling an invasion of privacy? Why or why not? The current controversy (Facebook and Cambridge...
-
Let (x) = x 2 - 9, g(x) = 2x, and h(x) = x - 3. Find each of the following. (((--) 2
-
The data shown in the following table were obtained from the 1990 Census. Included is information on 26 randomly selected Metropolitan Statistical Areas (MSAs). Of interest are factors that...
-
Answer the same questions as in parts (a) and (b) of Problem 1 for each of the regressions of Y on X in Problems 5 through 8 and Problem 10 of Chapter 5. The following results will be helpful:...
-
Assume that Z is a normal random variable with mean 0 and variance I. a. P (Z 1) = ? b. P (Z ?) = .20
-
OMalley Corporation was incorporated and began business on January 1, 2015. It has been successful and now requires a bank loan for additional working capital to finance expansion. The bank has...
-
Presented below is information related to Viel Company at December 31, 2015, the end of its first year of operations. (a) income from operations, (b) net income, (c) net income attributable to Viel...
-
Financial Reporting Problem Marks and Spencer plc (M&S) The financial statements of M&S (GBR) are presented in Appendix A. The companys complete annual report, including the notes to the financial...
Study smarter with the SolutionInn App