Consider the following function: 1 def func(1st: List[int]) -> None: n = len(1st) i = 0...

 

Transcribed Image Text:

Consider the following function: 1 def func(1st: List[int]) -> None: n = len(1st) i = 0 j = 1 while i < n: if 1st (i] >= 0: i = i + j 2 3 4 7. else: = abs (1st (i] ) 1st [i] i = 0 j-j+ 2 10 11 (a) Find, with proof, an inmput family for func whose running time is O(log n). (b) Find, with proof, an input family for func whose running time is O(n) and for which the else branch (Lines 9-11) executes 2(log n) times. To simplify your analysis, you may assume n (the length of the list) is a power of 2.4 You may use the following formula, valid for all n eN and r eR where r + 1: n-1 1- r" Σ i-0 (c) Prove that the worst-case running time for func is O(n). Consider the following function: 1 def func(1st: List[int]) -> None: n = len(1st) i = 0 j = 1 while i < n: if 1st (i] >= 0: i = i + j 2 3 4 7. else: = abs (1st (i] ) 1st [i] i = 0 j-j+ 2 10 11 (a) Find, with proof, an inmput family for func whose running time is O(log n). (b) Find, with proof, an input family for func whose running time is O(n) and for which the else branch (Lines 9-11) executes 2(log n) times. To simplify your analysis, you may assume n (the length of the list) is a power of 2.4 You may use the following formula, valid for all n eN and r eR where r + 1: n-1 1- r" Σ i-0 (c) Prove that the worst-case running time for func is O(n).

Answer rating: 100% (QA)

Solution a for a running time of thetalognwe need to have negative values at every power of 2 index ... View the full answer