6. Here is the same pseudocode from the previous page. function mcs (A,L,R) if L == R else return (A [L]) C (L+R) // 2 Lmax = mcs (A,L,C) Rmax mcs (A,C+1,R) Smax print (Lmax, Smax, Rmax) straddle max of the (sub) list return (max ([Lmax, Rmax, Smax])) end end Suppose that calculating the straddle max takes time in seconds equal to the length of the (sub)list. We apply mcs to a list of length n = 2' for some j≥1. (a) Over the course of the algorithm the straddle max will be calculated for many different [10 pts] length (sub)lists. We want to construct a table which tells us what the (sub)list lengths are, how many there are of each, and how much time it takes to calculate the straddle max for all of each length together. Here is the table. Fill in the missing entries. All of these should be in terms of j: Sub(list) Length How Many of These Total Time for All of These 25 25-1 1 1 B (b) How many rows are in the table, in terms of j? [3 pts] How Many Rows? (e) In terms of n, how long will the algorithm take to run? [3 pts] Total Time?
6. Here is the same pseudocode from the previous page. function mcs (A,L,R) if L == R else return (A [L]) C (L+R) // 2 Lmax = mcs (A,L,C) Rmax mcs (A,C+1,R) Smax print (Lmax, Smax, Rmax) straddle max of the (sub) list return (max ([Lmax, Rmax, Smax])) end end Suppose that calculating the straddle max takes time in seconds equal to the length of the (sub)list. We apply mcs to a list of length n = 2' for some j≥1. (a) Over the course of the algorithm the straddle max will be calculated for many different [10 pts] length (sub)lists. We want to construct a table which tells us what the (sub)list lengths are, how many there are of each, and how much time it takes to calculate the straddle max for all of each length together. Here is the table. Fill in the missing entries. All of these should be in terms of j: Sub(list) Length How Many of These Total Time for All of These 25 25-1 1 1 B (b) How many rows are in the table, in terms of j? [3 pts] How Many Rows? (e) In terms of n, how long will the algorithm take to run? [3 pts] Total Time?
Related questions
Question
![6. Here is the same pseudocode from the previous page.
function mcs (A,L,R)
if L == R
else
return (A [L])
C (L+R) // 2
Lmax = mcs (A,L,C)
Rmax mcs (A,C+1,R)
Smax
print (Lmax, Smax, Rmax)
straddle max of the (sub) list
return (max ([Lmax, Rmax, Smax]))
end
end
Suppose that calculating the straddle max takes time in seconds equal to the length of the
(sub)list. We apply mcs to a list of length n = 2' for some j≥1.
(a) Over the course of the algorithm the straddle max will be calculated for many different [10 pts]
length (sub)lists. We want to construct a table which tells us what the (sub)list lengths
are, how many there are of each, and how much time it takes to calculate the straddle
max for all of each length together. Here is the table. Fill in the missing entries. All of
these should be in terms of j:
Sub(list) Length
How Many of These
Total Time for All of These
25
25-1
1
1
B
(b) How many rows are in the table, in terms of j?
[3 pts]
How Many Rows?
(e) In terms of n, how long will the algorithm take to run?
[3 pts]
Total Time?](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F6fb406b3-dfb5-4d65-a424-9ec71ae4c6de%2F0fe3cf1d-5779-441f-809b-809ef00d2c38%2Fx8r12df_processed.png&w=3840&q=75)
Transcribed Image Text:6. Here is the same pseudocode from the previous page.
function mcs (A,L,R)
if L == R
else
return (A [L])
C (L+R) // 2
Lmax = mcs (A,L,C)
Rmax mcs (A,C+1,R)
Smax
print (Lmax, Smax, Rmax)
straddle max of the (sub) list
return (max ([Lmax, Rmax, Smax]))
end
end
Suppose that calculating the straddle max takes time in seconds equal to the length of the
(sub)list. We apply mcs to a list of length n = 2' for some j≥1.
(a) Over the course of the algorithm the straddle max will be calculated for many different [10 pts]
length (sub)lists. We want to construct a table which tells us what the (sub)list lengths
are, how many there are of each, and how much time it takes to calculate the straddle
max for all of each length together. Here is the table. Fill in the missing entries. All of
these should be in terms of j:
Sub(list) Length
How Many of These
Total Time for All of These
25
25-1
1
1
B
(b) How many rows are in the table, in terms of j?
[3 pts]
How Many Rows?
(e) In terms of n, how long will the algorithm take to run?
[3 pts]
Total Time?
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 2 steps
