c. The code fragment below computes a table of maximum values over fixed sub-ranges of a given list. 1 2 3 4 5 6 7 8 def mkMaxTable (vec): n = len(vec) tbl = [vec] def helper (width): if width <= 1: return vec else: hw width // 2 a 9 prev Row helper (hw) row = [] for i in range (n - width): row. append(max (prevRow [i], prevRow [i + hw])) tbl.append(row) return row 10 11 12 13 14 15 16 helper (n) return tbl Let T(n) represent the (worst case) time complexity of mkMaxTable (vec), vec is some vector (list) and n is its length. Let Th(w) represent the worst case time complexity of helper (w). Use the set {+,-,*, //,%, <=, max, append} as the basic operations under consideration. (i) Derive a relationship between T and Th. (ii) Derive a recurrence relation defining Th(w). [2] [3]
c. The code fragment below computes a table of maximum values over fixed sub-ranges of a given list. 1 2 3 4 5 6 7 8 def mkMaxTable (vec): n = len(vec) tbl = [vec] def helper (width): if width <= 1: return vec else: hw width // 2 a 9 prev Row helper (hw) row = [] for i in range (n - width): row. append(max (prevRow [i], prevRow [i + hw])) tbl.append(row) return row 10 11 12 13 14 15 16 helper (n) return tbl Let T(n) represent the (worst case) time complexity of mkMaxTable (vec), vec is some vector (list) and n is its length. Let Th(w) represent the worst case time complexity of helper (w). Use the set {+,-,*, //,%, <=, max, append} as the basic operations under consideration. (i) Derive a relationship between T and Th. (ii) Derive a recurrence relation defining Th(w). [2] [3]
C++ Programming: From Problem Analysis to Program Design
8th Edition
ISBN:9781337102087
Author:D. S. Malik
Publisher:D. S. Malik
Chapter17: Linked Lists
Section: Chapter Questions
Problem 18PE
Related questions
Question
![c. The code fragment below computes a table of maximum values over fixed sub-ranges
of a given list.
1
2
3
4
5
6
7
8
def mkMaxTable (vec):
n = len(vec)
tbl =
[vec]
def helper (width):
if width <= 1:
return vec
else:
hw width // 2
a
9
prev Row
helper (hw)
row = []
for i in range (n - width):
row. append(max (prevRow [i], prevRow [i + hw]))
tbl.append(row)
return row
10
11
12
13
14
15
16
helper (n)
return tbl
Let T(n) represent the (worst case) time complexity of mkMaxTable (vec), vec is some
vector (list) and n is its length. Let Th(w) represent the worst case time complexity
of helper (w). Use the set {+,-,*, //,%, <=, max, append} as the basic operations
under consideration.
(i) Derive a relationship between T and Th.
(ii) Derive a recurrence relation defining Th(w).
[2]
[3]](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F252320e2-0730-4470-b43f-ccba1610467c%2F6a81132a-607f-4c3b-9b1e-d1f48776c7f9%2Fjy823nn_processed.png&w=3840&q=75)
Transcribed Image Text:c. The code fragment below computes a table of maximum values over fixed sub-ranges
of a given list.
1
2
3
4
5
6
7
8
def mkMaxTable (vec):
n = len(vec)
tbl =
[vec]
def helper (width):
if width <= 1:
return vec
else:
hw width // 2
a
9
prev Row
helper (hw)
row = []
for i in range (n - width):
row. append(max (prevRow [i], prevRow [i + hw]))
tbl.append(row)
return row
10
11
12
13
14
15
16
helper (n)
return tbl
Let T(n) represent the (worst case) time complexity of mkMaxTable (vec), vec is some
vector (list) and n is its length. Let Th(w) represent the worst case time complexity
of helper (w). Use the set {+,-,*, //,%, <=, max, append} as the basic operations
under consideration.
(i) Derive a relationship between T and Th.
(ii) Derive a recurrence relation defining Th(w).
[2]
[3]
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
Recommended textbooks for you
C++ Programming: From Problem Analysis to Program…
Computer Science
ISBN:
9781337102087
Author:
D. S. Malik
Publisher:
Cengage Learning
C++ Programming: From Problem Analysis to Program…
Computer Science
ISBN:
9781337102087
Author:
D. S. Malik
Publisher:
Cengage Learning