A. Consider the algorithm MyAlg below: Algorithm MyAlg (A, n) Input: Initialized Array A of integer containing n elements Output: Array S of integer containing n elements for i=0 to n-1 do Var[i]=0 end for for i=0 to n-2 do 1. 2. 3. 4. for j=i+1 to n-1 do if A[i]
A. Consider the algorithm MyAlg below: Algorithm MyAlg (A, n) Input: Initialized Array A of integer containing n elements Output: Array S of integer containing n elements for i=0 to n-1 do Var[i]=0 end for for i=0 to n-2 do 1. 2. 3. 4. for j=i+1 to n-1 do if A[i]
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
Topic Video
Question
please only answer part 1 (i) , 2 (ii) and 3 (iii)
data structure (java)
![A.
Consider the algorithm MyAlg below:
Algorithm MyAlg (A, n)
Input:
Initialized Array A of integer containing n elements
Output: Array S of integer containing n elements
for i=0 to n-1 do
Var[i]=0
end for
for i=0 to n-2 do
1.
2.
3.
4.
for j=i+1 to n-1 do
if A[i]<A[j] then
Var[j]= Var[j]+1
5.
6.
7.
8.
else
Var[i]= Var[i]+1
end if
end for
9.
10.
11.
end for
for i=0 to n-1 do
12.
13.
14.
S[Var[i]]= A[i]
15.
end for
16.
Return S
i) What does MyAlg do? Explain that clearly.
ii) What is the Big-O and Big-N time complexity for algorithm MyAlg in terms of n? You will
need to show all necessary steps – No mark will be given if details are missing.
iii) Trace (i.e. hand-run, or manually) MyAlg for an array A = {50, 25, 71, 88, 4, 37}. What is the
resulting array S? You must show how array S is filled as the algorithm progresses/runs.
iv) Can the runtime of MyAlg be improved easily? If no, explain why MyAlg produces the best
possible complexity. If yes, explain how this can be done (i.e. re-write another more efficient
solution that does exactly what MyAlg is doing).
v) What is the Big-O space complexity of MyAlg? Can the space complexity of MyAlg be
improved? If so, explain how? If not, explain why this is not possible.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F77362dc8-c3d0-412f-af73-de35a4e70e7b%2F4ed0b52e-465c-4462-af24-43b4edf0fa2a%2Fegfvn6h.jpeg&w=3840&q=75)
Transcribed Image Text:A.
Consider the algorithm MyAlg below:
Algorithm MyAlg (A, n)
Input:
Initialized Array A of integer containing n elements
Output: Array S of integer containing n elements
for i=0 to n-1 do
Var[i]=0
end for
for i=0 to n-2 do
1.
2.
3.
4.
for j=i+1 to n-1 do
if A[i]<A[j] then
Var[j]= Var[j]+1
5.
6.
7.
8.
else
Var[i]= Var[i]+1
end if
end for
9.
10.
11.
end for
for i=0 to n-1 do
12.
13.
14.
S[Var[i]]= A[i]
15.
end for
16.
Return S
i) What does MyAlg do? Explain that clearly.
ii) What is the Big-O and Big-N time complexity for algorithm MyAlg in terms of n? You will
need to show all necessary steps – No mark will be given if details are missing.
iii) Trace (i.e. hand-run, or manually) MyAlg for an array A = {50, 25, 71, 88, 4, 37}. What is the
resulting array S? You must show how array S is filled as the algorithm progresses/runs.
iv) Can the runtime of MyAlg be improved easily? If no, explain why MyAlg produces the best
possible complexity. If yes, explain how this can be done (i.e. re-write another more efficient
solution that does exactly what MyAlg is doing).
v) What is the Big-O space complexity of MyAlg? Can the space complexity of MyAlg be
improved? If so, explain how? If not, explain why this is not possible.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 3 steps with 4 images
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