2.) Let f() be a function defined on the positive integers. For some fixed unknown positive...

Transcribed Image Text:

2.) Let f() be a function defined on the positive integers. For some fixed unknown positive integer n, f(x)= -1 = 0 1 for 1<x< n for x = n for x > n. (1) Assume a single call to f() takes unit time. 1. Give a very simple algorithm that finds the value of n in O(n) time. 2. Design a more sophisticated algorithm that finds the value of n in o(n) time. What is the best running time you can achieve? 3. Can you give an argument for a lower bound on the running time of any algorithm that finds the value of n? 2.) Let f() be a function defined on the positive integers. For some fixed unknown positive integer n, f(x)= -1 = 0 1 for 1<x< n for x = n for x > n. (1) Assume a single call to f() takes unit time. 1. Give a very simple algorithm that finds the value of n in O(n) time. 2. Design a more sophisticated algorithm that finds the value of n in o(n) time. What is the best running time you can achieve? 3. Can you give an argument for a lower bound on the running time of any algorithm that finds the value of n?

Answer rating: 100% (QA)

Solution to Problem 2 1 Simple algorithm to find n in On time def findnf for x in range1 n ... View the full answer