Data Structures and Algorithms in Java
Data Structures and Algorithms in Java
6th Edition
ISBN: 9781119278023
Author: Michael T. Goodrich; Roberto Tamassia; Michael H. Goldwasser
Publisher: Wiley Global Education US
bartleby

Concept explainers

Expert Solution & Answer
Book Icon
Chapter 4, Problem 60P

Explanation of Solution

Experimental analysis for prefixAverage1:

With the reference to the textbook, the prefixAverage1 algorithm computes the prefix averages in quadratic time O(n2). Now let us take the given algorithm from the textbook for analysis to draw the visualization representation as follows:

Algorithm: prefixAverage1(X,n)

Input: array x on n integers

Output: Array A of prefix averages of X

//Line1

A<- new array of n integers

//Line2

for i<-0 to n-1 do

  //Line3

  S<-X[0]

  //Line4

  for j<-1 to i do

  //Line5

  S<-S+X[j]

  // Line6

  A[i]<-s/(i+1)

//Line7

return A

Explanation:

In the above algorithm,

  • The Line1 is to initialize the array of “n” integers and it takes O(n) time.
  • Next the Line2 is the outer for loop which act as counter and executed “n” number of times and it takes O(n) times to complete the loop.
  • The Line3 is assigning the initial element of array to variable “s” and this executes in O(n) time.
  • Line4 is the inner body of for loop executes based on the outer for loop and it follows sum up operation such as 1+2+3+…(n-1). So, this line executes in O(n2) time.
  • Similar to Line4 and Line 5 follows same running time O(n2) because it performs sum up operation inside the for loop.
  • On Line6, it calculates the averages for the sum of elements and this is executed in O(n) time because the operation is directly proportional.
  • On Line7, the value is returned and it is executed in constant time O(1).

Visualization representation of algorithm prefixAverage1 in log-log graph:

As the running time of prefixAverage1 is O(1+2++n) and the sum of first “n” integers is n(n+1)2

Blurred answer
Students have asked these similar questions
Create 6 users: Don, Liz, Shamir, Jose, Kate, and Sal. Create 2 groups: marketing and research. Add Shamir, Jose, and Kate to the marketing group. Add Don, Liz, and Sal to the research group. Create a shared directory for each group. Create two files to put into each directory: spreadsheetJanuary.txt meetingNotes.txt Assign access permissions to the directories:  Groups should have Read+Write access Leave owner permissions as they are  “Everyone else” should not have any access   Submit for grade: Screenshot of  /etc/passwd contents showing your new users Screenshot of /etc/group contents showing new groups with their members Screenshot of shared directories you created with files and permissions
⚫ your circuit diagrams for your basic bricks, such as AND, OR, XOR gates and 1 bit multiplexers, ⚫ your circuit diagrams for your extended full adder, designed in Section 1 and ⚫ your circuit diagrams for your 8-bit arithmetical-logical unit, designed in Section 2. 1 An Extended Full Adder In this Section, we are going to design an extended full adder circuit (EFA). That EFA takes 6 one bit inputs: aj, bj, Cin, Tin, t₁ and to. Depending on the four possible combinations of values on t₁ and to, the EFA produces 3 one bit outputs: sj, Cout and rout. The EFA can be specified in principle by a truth table with 26 = 64 entries and 3 outputs. However, as the EFA ignores certain inputs in certain cases, it is easier to work with the following overview specification, depending only on t₁ and to in the first place: t₁ to Description 00 Output Relationship Ignored Inputs Addition Mode 2 Coutsjaj + bj + Cin, Tout= 0 Tin 0 1 Shift Left Mode Sj = Cin, Cout=bj, rout = 0 rin, aj 10 1 1 Shift Right…
Show the correct stereochemistry when needed!! mechanism: mechanism: Show the correct stereochemistry when needed!! Br NaOPh diethyl ether substitution

Chapter 4 Solutions

Data Structures and Algorithms in Java

Knowledge Booster
Background pattern image
Computer Science
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
SEE MORE QUESTIONS
Recommended textbooks for you
Text book image
C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning
Text book image
C++ for Engineers and Scientists
Computer Science
ISBN:9781133187844
Author:Bronson, Gary J.
Publisher:Course Technology Ptr
Text book image
Programming Logic & Design Comprehensive
Computer Science
ISBN:9781337669405
Author:FARRELL
Publisher:Cengage
Text book image
Operations Research : Applications and Algorithms
Computer Science
ISBN:9780534380588
Author:Wayne L. Winston
Publisher:Brooks Cole
Text book image
Systems Architecture
Computer Science
ISBN:9781305080195
Author:Stephen D. Burd
Publisher:Cengage Learning
Text book image
EBK JAVA PROGRAMMING
Computer Science
ISBN:9781305480537
Author:FARRELL
Publisher:CENGAGE LEARNING - CONSIGNMENT