I don't understand How it has reduced the time complexity?

#1

I don’t understand How it has reduced the time complexity? Can You Please explain why use of upper bound decreased the upper bound frequency.

#2

Since Dp array is strictly increasing(means it is sorted). So binary search can be applied. You must know that binary search is a O(log n) operation. Previously we were doing linear search which was O(n).
This way upper bound(binary search) reduces the overall complexity to O(n logn)

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.