Give a big-Oh characterization, in terms of n, of the running time of the example 5 function
Question:
Give a big-Oh characterization, in terms of n, of the running time of the example 5 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: 50% (8 reviews)
Consider the number of times the inner ...View the full answer
Answered By
Sheikh Muhammad Ibrahim
During the course of my study, I have worked as a private tutor. I have taught Maths and Physics to O'Level and A'Level students, as well as I have also taught basic engineering courses to my juniors in the university. Engineering intrigues me alot because it a world full of ideas. I have passionately taught students and this made me learn alot. Teaching algebra and basic calculus, from the very basics of it made me very patient. Therefore, I know many tricks to make your work easier for you. I believe that every student has a potential to work himself. I am just here to polish your skills. I am a bright student in my university. My juniors are always happy from me because I help in their assignments and they are never late.
4.90+
14+ Reviews
24+ 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.
-
Give an example of each type of function. (a) Linear function (b) Power function (c) Exponential function (d) Quadratic function (e) Polynomial of degree 5 (f) Rational function
-
Give an example of a Code provision with limiting language other than For purposes of this Section. How does the limitation affect the application of the provision you found?
-
Gamma Company adjusts its accounts at the end of each month. The following information has been assembled in order to prepare the required adjusting entries at December 31:1. A one-year bank loan of...
-
A student bought a $75 used guitar and agreed to pa: for it with a single $85 payment at the end of 6 months Assuming semiannual (every 6 months) compounding, what is the nominal annual interest...
-
Company N, an accrual basis taxpayer, owes $90,000 to Creditor K. At the end of 2021, Company N accrued $7,740 interest payable on this debt. It didnt pay this liability until March 3, 2022. Both...
-
Extreme Machine manufactures machines and parts for various industries; they have an office in Youngstown, Ohio. Avery Dennison manufactures and sells labels from a plant in Mentor, Ohio. They use...
-
During 2011, Rooster Company purchased 5,000 shares of Hen Company common stock for $18 per share and 3,200 shares of Egg Company common stock for $21 per share. These investments are intended to be...
-
Robert purchased US$15,000 from a bank in America, which charged him a commission of 0.9%, and sold the US dollars to a bank in Canada, which charged him a 0.24% commission. How much money did he...
-
Ida Company produces a handcrafted musical instrument called a gamelan that is similar to a xylophone. The gamelans are sold for $886. Selected data for the company's operations last year follow:...
-
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 =...
-
Given an n-element sequence S, Algorithm D calls Algorithm E on each element S[i]. Algorithm E runs in O(i) time when it is called on element S[i]. What is the worst-case running time of Algorithm D?
-
A 'one-for-one' or 100 percent time participation plan for incentive payment is in operation. The operator base rate for this class of work is $10.40. The base rate is guaranteed. Compute: a. Total...
-
Geoff opens an account for $250,000 at Home Federal Bank. The account provides that the funds are held in trust for Isabella, Geoff's daughter, and will be passed to her upon his death. What is...
-
How a Company has a deferred compensation plan? Explain the company's compensation in detail. What pays $0 for 2 years and then $2,100 in Year 3. For Year 4 onward, pays $700 annually. Tax allows...
-
What are the general and local indicators conditions that may impact the estimated selling price at property?
-
What is the time reported when multiple surgical procedures are performed during a single anesthetic administration? Discuss
-
How a standard process describes the fundamental process elements? What are expected steps taken incorporated into any defined process .?
-
Why is cash flow planning so important?
-
If the amplifier indicated by the box input impedance of oo, which of the following statements are true ? has an open loop gain as well as Feedback factor (\beta = 1/ R_1\) The feedback is voltage...
-
Consider a deletion operation in an AVL tree that triggers a trinode restructuring for the case in which both children of the node denoted as y have equal heights. Give a schematic figure, in the...
-
Draw the AVL tree resulting from the removal of the entry with key 62 from the AVL tree of Figure 11.13b. 4 62 44 78) 50 88 48 54 T4 T2 (b)
-
Draw the AVL tree resulting from the insertion of an entry with key 52 into the AVL tree of Figure 11.13b. 4 62 44 78) 50 88 48 54 T4 T2 (b)
-
The controller for Tulsa Medical Supply Company has established the following activity cost pools and cost drivers. Machine setups Budgeted Overhead Cost Cost Driver Number of setups Weight of raw...
-
In 2023, Miranda records net earnings from self-employment of $168,500. She has no other income. Determine the amount of Miranda's self-employment tax and her AGI income tax deduction. In your...
-
Describe how empowerment, work groups, and multifunctional teams would or would not affect the five types of problems.
Study smarter with the SolutionInn App