Monotonic function

1. A monotonic function is a mathematical function that either always increases or always decreases as its input values change. In other words, if increasing values of the input variable result in either strictly increasing or decreasing values of the output variable, then the function is said to be monotonic. The function mentioned above is monotonic, meaning that it always increases.
1. The rate of change can vary between functions and does not affect their monotonicity. While the Sqrt(x) function always increases, it does so at a slower rate for higher values of x.


Courtesy: https://www.desmos.com/calculator

2. Just like a quadratic function with a (x^2) term that always increases but at a faster rate, the function is also monotonically increasing on the interval [0, ∞).


Courtesy: https://www.desmos.com/calculator

2. Unlike monotonic functions, non-monotonic functions can increase or decrease for increasing values of x.

3. Here are some real-life examples of monotonicity
1. Increasing
• Your weight will increase when your mass will increase.
• The speed of the car will increase when the power of the engine increases
• The number of how many goods you can produce in an hour will increase if you hire more workers.
2. Decreasing
• The level of friction in an aircraft reduces as we increase in height in the atmosphere.
• The time it will take to produce a fixed number of goods (ex 100 cars) will decrease as you hire more workers
• The time taken to eat 4 piles decreases, As we increase the speed of banana consumption per hour (example from a question we will do 🐒KOKO eating Bananas )

Real-world scenarios involve various nuances, such as diminishing marginal returns with goods produced and increased friction at higher speeds, which have not been taken into account in the examples mentioned above. Currently, only a one-dimensional(Univariate) version of these scenarios is being considered.

Why is this relevant in Binary Search?

1. In the next few questions, binary search will are looking for a certain threshold in a monotonic function(usually the first feasible value). A threshold is a specific value of "y" that separates feasible and infeasible solutions.
1. Feasible, if we are on a feasible value and the monotonic function is decreasing we will know the first feasible value might be to the left.
2. Unfeasible, if we are on an Unfeasible value and the monotonic function is decreasing we will know the first feasible value might be to the right.

KOKO eating Bananas

SQRT(X)—Square Root Estimation

Allocate a minimum number of pages (Hard)

2. An example from KOKO eating Bananas: As the threshold was a specific value of hours after the guard was going to come back, we needed to find the least speed that is feasible (so we can eat bananas before the guard comes back). This will be the first value after the threshold of "y" (the time the guard comes back).

3. Questions involving a monotonic function often require finding the optimal value(first feasible or last unfeasible) for variables such as speed and quantity. This is done by determining the value of x when it produces a value near the threshold in terms of y. While this may seem abstract, examining the questions in the "Similar questions" section of KOKO eating Bananas shows how using logarithmic time can reduce the range by hopping between feasible and unfeasible values of y, ultimately narrowing the range and aiding in the discovery of the optimized value.
4. Let's revisit some examples with a threshold.
1. Increasing
• The speed of the car will increase when the power of the engine increases.
• What will be the least engine power (x) needed to bring the car speed (y) to supersonic speed (threshold)?
• The number of goods you can produce in an hour will increase if you hire more workers.
• What will be the least number of workers (x) needed to break the record (threshold) of goods(y) produced last year?
2. Decreasing
• The time is taken to eat 4 piles decreases as we increase the speed of banana consumption per hour (for example from a question we will do KOKO eating Bananas ).
• Return the minimum integer k (speed) such that she can eat all the bananas before the guard comes back (threshold) in h hours (y).