Give a big-Oh characterization, in terms of n, of the running time of the example3 function shown
Question:
Give a big-Oh characterization, in terms of n, of the running time of the example3 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: 57% (14 reviews)
Consider the number of times the inner ...View the full answer
Answered By
Muhammad Umair
I have done job as Embedded System Engineer for just four months but after it i have decided to open my own lab and to work on projects that i can launch my own product in market. I work on different softwares like Proteus, Mikroc to program Embedded Systems. My basic work is on Embedded Systems. I have skills in Autocad, Proteus, C++, C programming and i love to share these skills to other to enhance my knowledge too.
3.50+
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
-
In a recent survey, 80% of the community favored building a police substation in their neighborhood. If 20 citizens are chosen, what is the mean and standard deviation for the number favoring the...
-
What interest rate, compounded quarterly, is equivalent to a 9.31% effective interest rate?
-
Rhea Xu is a self-employed professional singer. She resides in a rented apartment and uses one room exclusively as a business office. This room includes 225 of the 1,500 square feet of living space...
-
In February 2014, defendant Ibrahim M. Shihadeh, d/b/a Creative Designs Kitchen and Baths, agreed to purchase 25% of his anticipated natural gas needs at a fixed price for the 201415 and 201516...
-
The Conch Oil Company needs to transport 30 million barrels of crude oil from a port in Doha, Qatar in the Persian Gulf to three refineries throughout Europe. The refineries are in Rotterdam,...
-
A company is planning to manufacture snowboards. The fixed costs are $129 per day and the total costs are $5,897 per daily output of 18 boards. What is the average costs per board tend to as...
-
a. Complete the traffic table in Figure 3-13. b. In Figure 3-12, add 392 Mbps of traffic for Seattle-Ogden communication. Using a picture like the one in the figure, show your work. c. Do it again...
-
Give a big-Oh characterization, in terms of n, of the running time of the example 2 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 example4 function shown in Code Fragment 3.10. 1 def example1(S): "Return the sum of the elements in sequence S.""" n =...
-
This appendix shows how increased government purchases, with net taxes held constant, can eliminate a recessionary gap. How could a tax cut achieve the same result? Would the tax cut have to be...
-
What are the identifiable sources of Reported Unit Cost Accuracy Gap (RUCAG) given Wilkerson's standard cost system?
-
If a companies current ratio went from 1.40 one year to 1.22 the following year, what does that mean for the company?
-
Paul Daze Growers accumulated actual MOH costs this year of $ 4 8 , 8 8 0 , even though it had budgeted $ 5 4 , 8 1 0 of MOH. It allocates MOH based on the direct labor hours of its workers. At the...
-
The following information is available for Shanahan Company for the current year: The cash outflow to purchase Inventory through Accounts payable 2 5 0 , 0 0 0 Beginning Balance Ending Balance...
-
On January 1, 2023, Continuous Computing leased a set of servers from Harry's Hardware with annual payments of $26,000 for 4 years. The servers are expected to have a useful life of 6 years and have...
-
Why do some people have difficulty saving?
-
The words without recourse on an indorsement means the indorser is: a. not liable for any problems associated with the instrument. b. not liable if the instrument is dishonored. c. liable personally...
-
Suppose that we have made kn total accesses to the elements in a list L of n elements, for some integer k 1. What are the minimum and maximum number of elements that have been accessed fewer than k...
-
Given the set of element {a,b,c,d,e, f } stored in a list, show the final state of the list, assuming we use the move-to-front heuristic and access the elements according to the following sequence:...
-
The java.util.Collection interface includes a method, clear( ), that removes all elements from a collection. Implement such a method in the ArrayList class of Section 7.2.
-
The density of the block depends on what material the block is made out of. The table below shows the average densities for 3 different kinds of Earth materials. Using these data, calculate the...
-
The hydrogen spectrum shows 4 lines in the region visible spectral (this series is called the Balmer series: H (red): =656.3 nm, H(blue-green): = 481.1 nm, H (purple): = 434.1 nm, and H(purple): =...
-
A ring-shaped conductor with radius a = 2.50 cm has a total positive charge Q=0.123 nC uniformly distributed around it. (Eigure 1) What is the magnitude of the electric field at point P, which is on...
Study smarter with the SolutionInn App