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
-
A company's income statement for the year to 31 March 2018 is as follows: Notes: 1) The company acquired 240,000 of 10% debentures (for non -trade purposes) on 1 January 2018. Interest is receivable...
-
Since Oreo cookies are the featured product in the twist, lick, and dunk ritual, the Oreo cookie could be considered a __________. a. gift-giving product b. normcore c. fortress brand d. fad e....
-
Journal entries for convertible bonds. Higgins Corporation issues $1 million of 20-year, $1,000 face value, 10% semiannual coupon bonds at par on January 2, 2008. Each $1,000 bond is convertible into...
-
You must demonstrate your knowledge of WHS within a workplace environment by answering the following questions in the spaces provided based on your experiences while on work placement. Ensure you...
-
Two astronomers in different parts of the world make measurements M1 and M2 of the number of stars N in some small region of the sky, using their telescopes. Normally. There is a small possibility e...
-
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 =...
-
Consider a hypothetical microprocessor generating a 16-bit address (e.g., assume that the program counter and the address registers are 16 bits wide) and having a 16-bit data bus. a. What is the...
-
Marie is thinking of two numbers. When she adds, she gets 40. When she multiplies them, she gets 351. She Helps her younger sister, Enya, calculate the numbers.
-
For the tax year 2 0 2 3 / 2 4 Keith has net income of 1 1 2 6 7 5 and paid 8 1 5 to charity under the gift aid scheme. What will be his personal allowance for the year? Enter a whole number, without...
-
A beverage producer produces two products, an orange beverage containing 10% orange juice and an orange delight containing 50% orange juice. How many gallons of orange delight should be mixed with...
-
1- A particle of mass m = 0.40 kg attached to a thin rope is moving at constant speed, v = 5 m/s on a circular path, R = 0.50 m, while a tension is exerted on the rope, see the figure. (a) Find the...
-
A new online music service has a collection of 1,500 songs. It expects to triple the number of songs each year for the next few years. Write an equation representing the relationship, where x is time...
-
For each of the following independent transactions, indicate the change in total assets. a. Purchased $750 of supplies on account. b. Paid cash to employees for their salaries, $5,000. c. Purchased...
-
Which should drive action planning more, strengths or weaknesses? That is, is it more important to build on your strengths or to reduce your weaknesses? Explain.
-
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...
-
A force F is acting on a body as it moves between (0, 0) and (1, 1). If the force is Evaluate the work done when the path is a) Along the line y=x F = (xy)+(x)j b) Along the curve y=x" c) Along the x...
-
Write a well-developed paragraph, summarizing the physical development of the observed 4-year-old child. Students must discuss at least 4 specific objective observations from their time spent...
-
An open cylindrical tank is 150 feet in diameter and 180 feet high.The side surface area of the tank (without top and bottom) should be painted with paint that covers 225 square feet per gallon.When...
Study smarter with the SolutionInn App