Give a big-Oh characterization, in terms of n, of the running time of the example4 function shown
Question:
Give a big-Oh characterization, in terms of n, of the running time of the example4 function shown in Code Fragment 3.10.
Transcribed Image Text:
1 def example1(S): "Return the sum of the elements in sequence S.""" n = len(S) total = 0 2 3 4 for j in range(n): total += S[j] # loop from 0 to n-1 5 6. return total 9 def example2(S): "Return the sum of the elements with even index in sequence S.""" n = len(S) total = 0 for j in range(0, n, 2): total += S[j] 10 11 12 # note the increment of 2 13 14 15 return total 16 def example3(S): """ Return the sum of the prefix sums of sequence S."" n = len(S) 17 1111 18 19 total = 0 20 for j in range(n): for k in range(1+j): total += S[k] # loop from 0 to n-1 # loop from 0 to j 21 22 23 24 return total 25 26 def example4(S): """Return the sum of the prefix sums of sequence S.""" n = len(S) prefix = 0 total = 0 27 28 29 30 for j in range(n): prefix += S[j] total += prefix 31 32 33 return total 34 35 36 def example5(A, B): """Return the number of elements in B equal to the sum of prefix sums in A.' n = len(A) # assume that A and B have equal length 37 38 39 count = 0 for i in range(n): total = 0 # loop from 0 to n-1 40 41 for j in range(n): for k in range(1+j): total += A[k] if B[i) == total: count += 1 # loop from 0 to n-1 # loop from 0 to j 42 43 44 45 %3D3%3= 46 47 return count Code Fragment 3.10: Some sample algorithms for analysis.
Fantastic news! We've Found the answer you've been seeking!
Step by Step Answer:
Answer rating: 40% (5 reviews)
Consider the number of times the inner ...View the full answer
Answered By
Joemar Canciller
I teach mathematics to students because I love to share what I have in this field.
I also want to see the students to love math and be fearless in this field.
I've been tutoring these past 2 years and I would like to continue what I've been doing.
5.00+
1+ Reviews
10+ Question Solved
Related Book For
Data Structures and Algorithms in Python
ISBN: 978-1118290279
1st edition
Authors: Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser
Question Posted:
Students also viewed these Computer science questions
-
Find an expression, in terms of n and the fundamental constants, for the de Broglie wavelength of an electron in the nth state of the hydrogen atom.
-
A fragment of the source code for a Binary Search Tree (BST) in JavaScript is given down below: class Node { constructor(val){ this.val = val this.left = null this.right = null } } class BST {...
-
Give the m/z values of the fragment ions expected from b - type fragmentation of an M + 1 ion of the peptide N - F - E - S - G - K
-
1- The z-axis carries filamentary current of 10. A. Find Hat (-3,74,0) ? p= = = 2- The Y-axis carries filamentary current of 10 A. Find H at (-3,4,1) ? p= ,= = p= , = H p= 3- The X-axis carries...
-
Use a 15% interest rate to compute the value of P is the diagram. 50 7080
-
Acme is an accrual basis corporation. Mrs. Torres, Acmes chief financial officer, is a cash basis individual. In December 2021, Acmes board of directors decided that Mrs. Torres should receive a...
-
Plaintiff visited South Chicago on January 10, 2008, seeking a new 2008 Nissan Versa (Versa) with manual transmission, anti-lock brakes, and other features. He was told by the employees of South...
-
(Multiple-step and Extraordinary Items) The following balances were taken from the books of Maria Conchita Alonzo Corp. on December 31, 2004. Interest revenue $ 86,000 Accumulated depreciation...
-
Before boarding her flight to Zurich, Switzerland, Mary purchased CHF850 from her bank when the exchange rate was C$1 = CHF0.9651. However, Mary had to cancel the trip. Mary returned to the bank to...
-
Base-promoted hydrolysis of methyl mesitoate occurs through an attack on the alcohol carbon instead of the acyl carbon: (a) Can you suggest a reason that accounts for this unusual behavior? (b)...
-
Give a big-Oh characterization, in terms of n, of the running time of the example3 function shown in Code Fragment 3.10. 1 def example1(S): "Return the sum of the elements in sequence S.""" n =...
-
Give a big-Oh characterization, in terms of n, of the running time of the example 5 function shown in Code Fragment 3.10. 1 def example1(S): "Return the sum of the elements in sequence S.""" n =...
-
Suppose you are a systems analyst developing a detailed test plan. Explain the testing strategies you will use in your plan. Will you use live or simulated data?
-
Describe the difference between pre-money and post-money valuation. In what settings are investors most likely to focus on pre-money valuation, and when on post-money valuation?
-
The US federal minimum wage has been a topic of debate for decades. Some argue that raising the minimum wage will lead to job losses, while others believe it will boost the economy. Analyze the...
-
Calculate the break - even units if fixed costs are $ 1 2 , 0 0 0 and coffee has a price and cost of $ 3 . 3 0 and $ 0 . 5 0 per cup, respectively. How many units?
-
In a post-investment audit of a capital project, the revenue is $223,560, COGS is 6% of revenue, and operating income is $75,500, and the initial investment was $515,000. How much would the selling,...
-
Reid Company acquires copyrights from authors, paying advance royalties in some cases, and in others, paying royalties within 3 0 days of year - end. The following are included in the December 3 1...
-
List five reasons for saving?
-
Avatar Financials, Inc., located on Madison Avenue, New York City, is a company that provides financial advice to individuals and small- to mid-sized businesses. Its primary operations are in wealth...
-
The java.util.Collection interface includes a method, contains(o), that returns true if the collection contains any object that equals Object o. Implement such a method in the ArrayList class of...
-
Describe a fast recursive algorithm for reversing a singly linked list L, so that the ordering of the nodes becomes opposite of what it was before.
-
Communication security is extremely important in computer networks, and one way many network protocols achieve security is to encrypt messages. Typical cryptographic schemes for the secure...
-
What are the main role of a businessmen to build the good business relation and communication to make the business better everyday?
-
Let's assume your lab balloons, when filled with air, each had a mass of 3.00 grams. In a variation of your lab activity, you attach one of these balloons to a string such that the distance from the...
-
Samantha normally requires 1 3 7 0 0 kJ ( about 3 2 7 4 Calories ) of food energy per day. If Samantha consumes 1 4 3 8 5 kJ per day, she will steadily gain weight. How much time must Samantha spend...
Study smarter with the SolutionInn App