(a) Consider the following pseudocode: 1 // Assume n is a positive integer 2 for i:=...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
(a) Consider the following pseudocode: 1 // Assume n is a positive integer 2 for i:= 1 to n do 3 for j=1 to n do // ... Some constant time operations... To formally prove a tight upper bound on the runtime of this code, we can represent the number of steps it executes as a function of the input size n with summations. Say the total cost of the constant time operations in the inner loop is some positive constant c. The total runtime of this code will then be 1=1c. We can simplify this summation as Σ1 Σ=1= Σ=1 en = cn?. If no = 1 and c is our constant, then clearly cn² = O(n²), so this gives us a tight upper bound on the runtime of this nested loop. Prove a tight upper bound on the following pseudocode using summations, as above: 1 // Assume n is a positive integer 2 for i:= 1 to n do 3 for j=1 to i do // ...Some constant time operations... (b) Prove a tight upper bound on the following pseudocode using summations, as above: 1 // Assume n is a positive integer 2 for i:= 1 to n do 3 for j = i to n do // ...Some constant time operations... Note that j now goes from i to n. (a) Consider the following pseudocode: 1 // Assume n is a positive integer 2 for i:= 1 to n do 3 for j=1 to n do // ... Some constant time operations... To formally prove a tight upper bound on the runtime of this code, we can represent the number of steps it executes as a function of the input size n with summations. Say the total cost of the constant time operations in the inner loop is some positive constant c. The total runtime of this code will then be 1=1c. We can simplify this summation as Σ1 Σ=1= Σ=1 en = cn?. If no = 1 and c is our constant, then clearly cn² = O(n²), so this gives us a tight upper bound on the runtime of this nested loop. Prove a tight upper bound on the following pseudocode using summations, as above: 1 // Assume n is a positive integer 2 for i:= 1 to n do 3 for j=1 to i do // ...Some constant time operations... (b) Prove a tight upper bound on the following pseudocode using summations, as above: 1 // Assume n is a positive integer 2 for i:= 1 to n do 3 for j = i to n do // ...Some constant time operations... Note that j now goes from i to n.
Expert Answer:
Answer rating: 100% (QA)
Solution To prove a tight upper bound on the runtime o... View the full answer
Related Book For
Income Tax Fundamentals 2013
ISBN: 9781285586618
31st Edition
Authors: Gerald E. Whittenburg, Martha Altus Buller, Steven L Gill
Posted Date:
Students also viewed these programming questions
-
4. If the company normally carries 50 bags as safety stock, determine the reorder point for the spice. 4. Benoit Corporation produces lawn chairs. In order to produce the frames for the furniture,...
-
List three specific parts of the Case Guide, Objectives and Strategy Section (See below) that you had the most difficulty understanding. Describe your current understanding of these parts. Provide...
-
The following additional information is available for the Dr. Ivan and Irene Incisor family from Chapters 1-5. Ivan's grandfather died and left a portfolio of municipal bonds. In 2012, they pay Ivan...
-
Can you find a function such that (-2) = -2, (2) = 6, and '(x) < 1 for all x? Why or why not?
-
In the future, when everyone has a home terminal connected to a computer network, instant public referendums on important pending legislation will become possible. Ultimately, existing legislatures...
-
Draw the game tree for the game of tic-tac-toe for the levels corresponding to the first two moves. Assign the value of the evaluation function mentioned in the text that assigns to a position the...
-
What can you do with a Reliance Electric loose rotor bar construction on which someone has swedged the bars?
-
Income statement information for 2011 for Pug Corporation and its 60 percent-owned subsidiary, Sev Corporation, is as follows: Intercompany sales for 2011 are upstream (from Sev to Pug) and total...
-
The Simmons Corporation's income statement is given below. SIMMONS CORPORATION Sales $231,000 Cost of goods sold 116,000 Gross profit 115,000 Fixed charges (other than interest) 29,700 Income before...
-
How might one employee coach or train another employee by use of Twitter and text messaging?
-
1) Mad Dog Fence company expects to sell 300 fences p/yr for $1000 each. Monthly sales are 20% cash and 80% credit. Operating expenses are: variable costs of $450 p/fence and annual fixed costs of...
-
Aiden works for a pharmaceutical company. It has been a little over 3 years since he was hired. He now makes $55,000 per year. When he was hired, he was told that he had 7 days of paid vacation time....
-
Winning the Best Entrepreneur Award for 2017 gave Othman and his team the boost to innovate further. They have also participated in exhibitions locally and internationally from London to China. Asked...
-
Raquel is presented with two loan options for a $60,000 student loan. Option A is a 10-year fixed rate loan with an annual interest rate of 4%, while Option B is a 20-year fixed-rate loan with an...
-
Reflect on projects that you have been involved in during your career(nursing) or in everyday life. We have all been involved in projects such as buying a house, renting an apartment, remodeling, and...
-
Value of an internationally traded product has different components with different magnitude. Would you please take a product that is produced in two different countries (e.g., USA and Canada), and...
-
Obtain all the Fourier coefficients of f(x) = k where k is a constant, the periodicity being 2TT. Solution. STED ONE
-
The first national bank pays a 4% interest rate compound continuously. The effective annual rate paid by the bank is __________. a. 4.16% b. 4.20% c. 4.08% d. 4.12%
-
Walter, a single taxpayer, purchased a limited partnership interest in a tax shelter in 1985. He also acquired a rental house in 2012, which he actively manages. During 2012, Walter's share of the...
-
If Charles, a 16-year-old child model, earns $50,000 a year and is completely self supporting even though he lives with his parents, can his parents claim him as a dependent? Why or why not?...
-
Robert Ramos (age 36) is a single taxpayer, living at 8765 Bay Dr., Monterey, CA 93940. His Social Security number is 976-23-5132. Robert's earnings and income tax withholding as the manager of a...
-
One of Hope Ltds customers has become insolvent. As a result the amount owed to Hope Ltd has become a bad debt. Which of the following is the consequence? A. Hope Ltds current ratio has increased. B....
-
For a company with no preference shares, earnings is the: A. Sales figure. B. Profit before tax. C. Profit after tax. D. Profit after tax and after dividends.
-
Repeat Exercise 1.4 from Chapter 1. Do you think that users know what to ask for from their accountant or financial adviser? Data from Repeat Exercise 1.4 Do you think that users know what to ask for...
Study smarter with the SolutionInn App