Give a big-Oh characterization, in terms of n, of the running time of the example1 function shown
Question:
Give a big-Oh characterization, in terms of n, of the running time of the example1 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: 25% (12 reviews)
Consider the number of times ...View the full answer
Answered By
Mugdha Sisodiya
My self Mugdha Sisodiya from Chhattisgarh India. I have completed my Bachelors degree in 2015 and My Master in Commerce degree in 2016. I am having expertise in Management, Cost and Finance Accounts. Further I have completed my Chartered Accountant and working as a Professional.
Since 2012 I am providing home tutions.
3.30+
2+ 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
-
The programming language is Java and all of the Classes I was given are in bold. ALIEN CLASS import imagePackage.RasterImage; import java.awt.BasicStroke; import java.awt.Color; import...
-
What amount will be required to purchase, on a man's 40th birthday, an annuity to provide him with 30 equal semiannual payments of $1000 each, the first to be received on his 50th birthday, if...
-
In each of the following cases, compute the corporations regular tax: a. Silva Corporation has $160,000 taxable income for its tax year ended December 31, 2017. b. Goyal Corporation has $160,000...
-
Should the requirements of the UCC be subject to the application of reliance theories? Go back and review the facts in Case 21-3 about the coal contract. Should silence followed by contract execution...
-
The general ledger of Pipers Plumbing at January 1, 2015, includes the following account balances: The following is a summary of the transactions for the year: a. Provide plumbing services for cash,...
-
(1) (a) Discretize the 2D Poisson equation Vu(x, y) = Uxx + Uyy = = p(x, y) with second-order accurate central differences with Ax = the given charge density. Ay=h. p(x, y) is (b) Express uij in...
-
Brothers Harry and Herman Hausyerday began operations of their machine shop (H & H Tool, Inc.) on January 1, 2010. The annual reporting period ends December 31. The trial balance on January 1, 2012,...
-
Show that n log n is (n).
-
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 =...
-
Depict graphically the aggregate expenditures model for a private closed economy. Now show a decrease in the aggregate expenditures schedule and explain why the decline in real GDP in your diagram is...
-
5. On the floor of a futures exchange one futures contract is traded where the long counterparty is closing out an existing position while the short counterparty to the contract is opening a new...
-
Can you elaborate on the role of familial socialization agents in shaping individual identities and interpersonal dynamics within family units?
-
Land is purchased for $125,000. The purchaser paid back taxes (past due) of $2,500, costs to demolish an existing byilding and clear the land of $62,500, and costs of paving to put in a parking lot...
-
Yellow? Company's variable expenses are 40% of sales and have monthly fixed expenses of $15,000. The monthly target operating income is $3,600. What is Yellow Company's operating leverage factor at...
-
Who is at a disadvantage for callable preferred stock, if a company decides to retire the preferred stock at a small premium over par?
-
Why do people construct a budget?
-
Al says he can prove that all sheep in a flock are the same color: Base case: One sheep. It is clearly the same color as itself. Induction step: A flock of n sheep. Take a sheep, a, out. The...
-
Alice has two circular queues,C and D, which can store integers. Bob givesAlice 50 odd integers and 50 even integers and insists that she stores all 100 integers in C and D. They then play a game...
-
Suppose Bob has four cows that he wants to take across a bridge, but only one yoke, which can hold up to two cows, side by side, tied to the yoke. The yoke is too heavy for him to carry across the...
-
1. Develop a definition for the Triple C model of project management. 2. List some of the factors that can impede the flow of information for project planning purposes. How can these factors be...
-
The Meat Mart has $900,000 in net income. The firm has 200,000 shares of stock outstanding. The market price per share is $76. What is the PE (price to earnings) ratio?
-
Cost of Goods Manufactured for a Manufacturing Company The following information is available for Fuller Manufacturing Company for the month ending January 31: Cost of direct materials used in...
Study smarter with the SolutionInn App