3. (24 pts; 6 each) Determine the worst-case execution time of each of the following methods...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
3. (24 pts; 6 each) Determine the worst-case execution time of each of the following methods as a function of the length of the input array(s). Express each of your answers as big-O of a simple function (which should be the simplest and slowest-growing function you can identify). For convenience, the analysis of each part has been broken down into multiple steps. For each step, you just need to fill in the blank a big-O function as the answer (in the worst case always). a) void methodA (int[] arr) { int p = 0; int n = arr.length; for (int i = 0; i<n; i++) { for (int j = i; j<n; j++) { Parr [j] % 2; } i) Number of iterations of the outer for loop: ii) Number of iterations of the inner for loop: iii) Worst-case execution time: b) Assume that the method foo () takes O(n²) time and method bar () takes O(n³) time. public static void methodB (int[] arr) { } int n = arr.length; while (n> 0) { foo (arr); n = n / 4: bar (arr) } i) Number of iterations of the while loop: ii) Time per iteration: iii) Total time for the while loop: iv) Total worst-case execution time for me thodB: 3. (24 pts; 6 each) Determine the worst-case execution time of each of the following methods as a function of the length of the input array(s). Express each of your answers as big-O of a simple function (which should be the simplest and slowest-growing function you can identify). For convenience, the analysis of each part has been broken down into multiple steps. For each step, you just need to fill in the blank a big-O function as the answer (in the worst case always). a) void methodA (int[] arr) { int p = 0; int n = arr.length; for (int i = 0; i<n; i++) { for (int j = i; j<n; j++) { Parr [j] % 2; } i) Number of iterations of the outer for loop: ii) Number of iterations of the inner for loop: iii) Worst-case execution time: b) Assume that the method foo () takes O(n²) time and method bar () takes O(n³) time. public static void methodB (int[] arr) { } int n = arr.length; while (n> 0) { foo (arr); n = n / 4: bar (arr) } i) Number of iterations of the while loop: ii) Time per iteration: iii) Total time for the while loop: iv) Total worst-case execution time for me thodB:
Expert Answer:
Answer rating: 100% (QA)
Lets analyze the given methods a methodAint arr i Number of iterations of the outer for loop n ii Nu... View the full answer
Related Book For
Systems Analysis And Design
ISBN: 978-1119496489
7th Edition
Authors: Alan Dennis, Barbara Wixom, Roberta M. Roth
Posted Date:
Students also viewed these programming questions
-
On December 1st, Johnson Company sold merchandise with a selling price of $2,000 on account to Mr. Thompson, with terms 2/10, n/30. Ignoring cost of goods sold, what journal entry did Johnson Company...
-
The following scenario was written by a reporter who became a Taco Bell worker for a few hours to experience what its like to work in the drive-thru window at one of the most high-tech, quick-serve...
-
The payroll project that follows is the online version of the same project you completed manually in Chapter 7 of your text. For this project, you will use the Cengage Learning General Ledger to...
-
A thermocouple Type K is calibrated in lab condition at 50% relative humidity (RH) prior to outdoor operation. After 12-month in outdoor installation, the thermocouple is again tested at 75% RH. Both...
-
Vector A has a negative x component 3.00 unit in length and a positive y component 2.00 units in length. (a) Determine an expression for A in unitvector notation. (b) Determine the magnitude and...
-
Rob Roy Corporation has, for the last three years, been using its present facilities at its annual full capacity of 10,000 units. Still, the company is unable to keep pace with continuing demand for...
-
What does a field technician need to be aware of when disconnecting the BNC connector on a proximeter of a loaded, running machine?
-
The Mona chino Manufacturing Company has the following budgeted overhead cost and other data for its machining department for the month of December: Budgeted Data: Indirect labor and supplies .....
-
Hoteliers have been hard at work to leave a positive first impression on their valued guests for decades. It is a pivotal element of a hotel's reputation, as how guests first perceive a hotel can set...
-
During the year, your clients Omar and Maria Mansour had the following investment transactions: Interest and dividend income reported to them: 1099-INT from Chase Bank Interest income (1099-INT from...
-
What are the four sales presentation methods discussed in this chapter? Briefly explain each method Give examples of where this sales presentation method would be used Describe similarities and...
-
My course product is the Breezy Blaster, a full-body automatic dryer that is compact and more affordable than those currently on the market. This product is ideal for college students or young adults...
-
5: Training Program with Variable Benefits A training program costs $30,000 to implement. It's expected to result in a $20,000 increase in revenue the first year, $35,000 the second year, and $45,000...
-
The following diagram shows the volumetric composition of a compacted HMA specimen. Please answer the following questions: (a) What do Vb, Vba: and Vsb stand for? (b) Write the equation usually used...
-
4) Write a program to sort two random arrays keyed in by the user into descending order, and merge them into a new array containing all the elements in the two arrays in descending order. Print the...
-
Each group is required to download and use the latest financial annual report (FYE 2022) of the selected company and refer to the "Group" / "Consolidated" financial data to answer the following...
-
Following details are related to the work done in Process 'A'XYZ Company during the month of March, 2011: (Rs.) 80,000 15,000 45,000 Opening work-in progress (2,000 units) Materials Labour Overheads...
-
Prove the formula for (d/dx)(cos-1x) by the same method as for (d/dx)(sin-1x).
-
Distinguish between a traditional ASP and a provider of software as a service. What are the pros and CMS of each solution approach?
-
Explain the purpose and contents of interface metaphors, interface objects, interface actions, interface icons, and interface templates.
-
Design a storyboard for Exercise I in Chapter 5.
-
Refer to the Example 4. Use calculus to obtain the location of the estimated maximum yield when all terms are included in the model. Data From Example 4 EXAMPLE 4 A response surface design to...
-
MINITAB response surface analysis We illustrate the commands for the coating data in Example 4 where yield is the response. Start with the Run, Additive, Temperature, Yield in C1-C4. Dialog box:...
-
The response variable \(Y_{i j}\) in a \(2^{2}\) design can also be expressed as a regression model \[Y_{i j}=\mu+\beta_{1} x_{1}+\beta_{2} x_{2}+\beta_{12} x_{1} x_{2}+\varepsilon_{i j}\] where the...
Study smarter with the SolutionInn App