we consider a monotonously decreasing function

Question

In this problem we consider a monotonously decreasing function f: N → Z (that is, a function defined on the natural numbers returning integer values, such that f(i) > f(i + 1)). Assuming we can evaluate f at any i in constant time O(1), we want to find n = min{i ∈ N | f(i) ≤ 0} (that is, we want to find the minimum value where f becomes negative).
We can obviously solve the problem in O(n) time by evaluating f(1), f(2), f(3), . . . f(n). However, I want you to describe an O(log n) divide-and-conquer algorithm to solve the problem. (Hint: Evaluate f on O(log n) carefully chosen values ≤ n and possibly at a couple of values between n and 2n).

Explanation

Here we will design an algorithm to solve the problem. For which we will use the divide and conquer algorithm. Such a that if we have to find a value for the minimum I. So at that time to solve the problem, we will calculate the value of f. With the 2n. Until we did not get the negative value. As we get the negative value we will stop.

f(0)
f(20 )=f(1) (a positive value)
f(21 )=f(2) (a positive value)
f(22 )=f(4) (a positive value)
. .
. .
. .
f(2n ) is a positive value
f(22n )<0 (first negative value for 2i )

So here we have complexity. The complexity of the search i.e. Binary search. So this is O(log n).

So that we divide the functions into two parts. They are :
⦁ Here first we have to find the value. This value is the negative value of f(i).
⦁ And next, we have to find the head of negative value i.e. between i=n and i=2n.

Here each part will have a time complexity of O(log n).

So the total complexity we have the complexity of the function is O(log n) + O(log n) = 2*O(log n)
Also, the final complexity we have is O(log n).

Also read, Must use header file, implementation file, the main program