Give a big-Oh characterization, in terms of n, of the running time of the example 2 function
Question:
Give a big-Oh characterization, in terms of n, of the running time of the example 2 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: 45% (11 reviews)
Consider the number of times ...View the full answer
Answered By
Subash Murugaih
I am leading expert in this web site couple of years and My clients are much happy with my works and services.
4.60+
309+ Reviews
539+ 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?
-
Steven Stores, Inc. provided the following statement of net income for the current year. All income is subject to a 40% income tax rate. The company also had $ 735 of unrealized holding gains on its...
-
A contractor wishes to set up a special fund by making uniform semiannual end-of-period deposits for 20 years. The fund is to provide $10,000 at the enc of each of the last 5 years of the 20-year...
-
In 2021, NB, Inc.s federal taxable income was $242,000. Compute the required installment payments of 2021 tax in each of the following cases: a. NBs 2022 taxable income is $593,000. b. NBs 2022...
-
This case deals with several issues regarding contract formation under the UCC. Logan and Kanawha Coal agreed to purchase coal from Detherage via a fax dated March 9, 2010. The fax stated that it had...
-
On January 1, 2017, the ledger of Accardo Company contains the following liability accounts. Accounts Payable ....... $52,000 Sales Taxes Payable....... 7,700 Unearned Service Revenue..... 16,000...
-
A bank in Toronto charges 2.2% commission to buy and sell currencies. Assume that the current exchange rate is US$1 = C$1.1153. a. How many Canadian dollars will you have to pay to purchase US$4,500?...
-
Discuss the differences between DDL and DML? What operations would you typically expect to be available in each language?
-
Give a big-Oh characterization, in terms of n, of the running time of the example1 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 example3 function shown in Code Fragment 3.10. 1 def example1(S): "Return the sum of the elements in sequence S.""" n =...
-
Express the following base 10 numbers in 12-bit fixed-point sign/ magnitude format with six integer bits and six fraction bits. Express your answer in hexadecimal. (a) 30.5 (b) 16.25 (c) 8.078125
-
How do religious institutions operate as socialization agents, transmitting moral values, belief systems, and rituals that contribute to individual and collective identity formation?
-
Dan Schmidt plans to invest in a rental property worth $240,000. He plans to hold the property for 4 years and expects to sell it for $280,000 at the end of the fourth year. He estimates that the...
-
3- How does the Accounts Payable controlling account in the general ledger relate to the accounts payable subsidiary ledger? 4- Why should a business closely monitor its accounts payable?
-
If your client approaches you for an opinion, can you cite a Private Letter Ruling as primary authority in their tax memorandum response? Why or why not?
-
List the variables underlying Black-Scholes option pricing model and point out how they affect option prices.
-
Provide five methods for helping people to save?
-
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.
-
Modify our ArrayList implementation to support the Cloneable interface, as described in Section 3.6.
-
Give an array-based list implementation, with fixed capacity, treating the array circularly so that it achieves O(1) time for insertions and removals at index 0, as well as insertions and removals at...
-
Implement a resetCounts( ) method for the FavoritesList class that resets all elements access counts to zero (while leaving the order of the list unchanged).
-
A 0.810-kg ball has a velocity of 4.16 m/s to the right. Calculate the momentum of the ball in kg m/s. What velocity does a 10.-g bullet need to have in order to have the same momentum as the ball?...
-
Develop a SWOT analysis of Coles potential business. b. Can Cole be profitable and if so, in what period of time? c. What are the major business assumptions that require verification? d. Does Cole,...
-
The current temperature is 12 oC and the dew point is -29 oC. What is the relative humidity in percentage? Answer to one decimal place. The current temperature is 12 oC and the dew point is -29 oC....
Study smarter with the SolutionInn App