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
I would like to get help to resolve the following case
Last Chance Securities The IT director opened the department staff meeting today by saying, "I've got some good news and some bad news. The good news is that management approved the payroll system project this morning. The new system will reduce clerical time and errors, improve morale in the payroll department, and avoid possible fines and penalties for noncompliance. The bad news is that the system must be installed by January 1st in order to meet new federal reporting rules, all expenses from now on must be approved in advance, the system should have a modular design if possible, and the vice president of finance would like to announce the new system in a year-end report if it is ready by mid-December." Tasks 1. Why is it important to define the project scope? How would you define the scope of the payroll project in this case? 2. Review each constraint and identify its characteristics: present versus future, internal versus exter- nal, and mandatory versus desirable. 3. What…
2. Signed Integers Unsigned binary numbers work for natural numbers, but many calculations use negative numbers as well. To deal with this, a number of different methods have been used to represent signed numbers, but we will focus on two's complement, as it is the standard solution for representing signed integers. 2.1 Two's complement • Most significant bit has a negative value, all others are positive. So, the value of an n-digit -2 two's complement number can be written as: Σ2 2¹ di 2n-1 dn • Otherwise exactly the same as unsigned integers. i=0 - • A neat trick for flipping the sign of a two's complement number: flip all the bits (0 becomes 1, or 1 becomes 0) and then add 1 to the least significant bit. • Addition is exactly the same as with an unsigned number. 2.2 Exercises For questions 1-3, answer each one for the case of a two's complement number and an unsigned number, indicating if it cannot be answered with a specific representation. 1. (15 pts) What is the largest integer…

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