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]
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
![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
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