Improving the efficiency of the algorithm

#1

could you explain… how we could solve this in O(nlogn)?

#2

@hv439606,
If you see closely, the only work the inner loop in the O(n^2) algorithm do is of finding the suitable maximum(i.e satisfying the strictly increasing constraint) from previous elements. So if you think again, finding this maximum can be done in log(n) by binary search. Thus total complexity = O(nlog(n)).

You will find these resources useful:

P.S, It is fairly complicated to understand at first go, you may have to read it multiple times to understand. If you find the explanation overwhelming, you can skip it for now, it isn’t that important.

#3

Hi @hv439606

do u have any doubts?
did u refer the to the links provided by the previous TA?

#4

Yes …I went through the links…and it’s clear now…thanks!

1 Like
#5

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.