You're given an array A consisting of n integers A[1], A[2], ...., A[n]. You'd like to output a two- dimensional n-by-n array B in which B[i, j] (for i < j) contains the sum of array entries A[i] through A[j] - that is, į A[k]. The value of the array entry B[i,j] is left unspecified whenever i ≥ j, so it doesn't matter what is output for these values. Here's a simple algorithm to solve this problem. for i= 1, 2, n for j =i+1, i + 2, ..., n Add up array entries A[i] through A[j] Store the result in B[i,j] endfor endfor a) For some function f that you should choose, give a bound of the form O(f(n)) on the running time of this algorithm on an input of size n (i.e., a bound on the number of operations performed by the algorithm). b) For the same function f, show that the function running time of the algorithm on an input of size n is also (f(n)). (This shows an asymptotically tight bound of (f(n)) on the running time.) c) Although the algorithm you analyzed in parts (a) and (b) is the most natural way to solve the problem - after all, it just iterates through the relevant entries of the array B, filling in a value for each - it contains some highly unnecessary sources of inefficiency. Give a different algorithm to solve this problem, with an asymptotically better running time. In other words, you should design g(n) an algorithm with running time O(g(n)), where limn→+∞ = 0. f(n)
You're given an array A consisting of n integers A[1], A[2], ...., A[n]. You'd like to output a two- dimensional n-by-n array B in which B[i, j] (for i < j) contains the sum of array entries A[i] through A[j] - that is, į A[k]. The value of the array entry B[i,j] is left unspecified whenever i ≥ j, so it doesn't matter what is output for these values. Here's a simple algorithm to solve this problem. for i= 1, 2, n for j =i+1, i + 2, ..., n Add up array entries A[i] through A[j] Store the result in B[i,j] endfor endfor a) For some function f that you should choose, give a bound of the form O(f(n)) on the running time of this algorithm on an input of size n (i.e., a bound on the number of operations performed by the algorithm). b) For the same function f, show that the function running time of the algorithm on an input of size n is also (f(n)). (This shows an asymptotically tight bound of (f(n)) on the running time.) c) Although the algorithm you analyzed in parts (a) and (b) is the most natural way to solve the problem - after all, it just iterates through the relevant entries of the array B, filling in a value for each - it contains some highly unnecessary sources of inefficiency. Give a different algorithm to solve this problem, with an asymptotically better running time. In other words, you should design g(n) an algorithm with running time O(g(n)), where limn→+∞ = 0. f(n)
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
100%
Help only for b and c, not question a
![You're given an array A consisting of n integers A[1], A[2], ..., A[n]. You'd like to output a two-
dimensional n-by-n array B in which B[i, j] (for i < j) contains the sum of array entries A[i] through
A[j] - that is, ; A[k].
k=i
The value of the array entry B[i,j] is left unspecified whenever i ≥ j, so it doesn't matter what
is output for these values.
Here's a simple algorithm to solve this problem.
for i = 1, 2, ... n
for j =i+1, i + 2, .... n
Add up array entries A[i] through A[j]
Store the result in B[i,j]
endfor
endfor
a) For some function f that you should choose, give a bound of the form O(f(n)) on the running
time of this algorithm on an input of size n (i.e., a bound on the number of operations performed
by the algorithm).
b) For the same function f, show that the function running time of the algorithm on an input of
size n is also (f(n)). (This shows an asymptotically tight bound of (f(n)) on the running time.)
c) Although the algorithm you analyzed in parts (a) and (b) is the most natural way to solve the
problem after all, it just iterates through the relevant entries of the array B, filling in a value
for each - it contains some highly unnecessary sources of inefficiency. Give a different algorithm to
solve this problem, with an asymptotically better running time. In other words, you should design
g(n)
an algorithm with running time O(g(n)), where limn→+∞
= 0.
f(n)
-](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F15d7109e-469c-48b5-b6f5-906596388e95%2Fb587263d-a533-404e-964a-4c6591a8b8ec%2F3tok4ik_processed.png&w=3840&q=75)
Transcribed Image Text:You're given an array A consisting of n integers A[1], A[2], ..., A[n]. You'd like to output a two-
dimensional n-by-n array B in which B[i, j] (for i < j) contains the sum of array entries A[i] through
A[j] - that is, ; A[k].
k=i
The value of the array entry B[i,j] is left unspecified whenever i ≥ j, so it doesn't matter what
is output for these values.
Here's a simple algorithm to solve this problem.
for i = 1, 2, ... n
for j =i+1, i + 2, .... n
Add up array entries A[i] through A[j]
Store the result in B[i,j]
endfor
endfor
a) For some function f that you should choose, give a bound of the form O(f(n)) on the running
time of this algorithm on an input of size n (i.e., a bound on the number of operations performed
by the algorithm).
b) For the same function f, show that the function running time of the algorithm on an input of
size n is also (f(n)). (This shows an asymptotically tight bound of (f(n)) on the running time.)
c) Although the algorithm you analyzed in parts (a) and (b) is the most natural way to solve the
problem after all, it just iterates through the relevant entries of the array B, filling in a value
for each - it contains some highly unnecessary sources of inefficiency. Give a different algorithm to
solve this problem, with an asymptotically better running time. In other words, you should design
g(n)
an algorithm with running time O(g(n)), where limn→+∞
= 0.
f(n)
-
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 4 steps
Knowledge Booster
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.Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education