Unpredictable loop variables. Consider the following function: def func (lst: List[int]) -> None: n = len...

 

 

Transcribed Image Text:

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

Answer rating: 100% (QA)

Answer Explanation a Guess the input that gives Olog n running time The all integers in the input li... View the full answer