In the link mentioned below , the last line of editorial says that the complexity of dp solution is O(len4) . But according to me it should be O(len4*8). Since for every state , we have 8 possible combinations and we are trying those using the three “for” loops inside the function .
Please see to this and let me know ?
link:
Complexity doubt from HackerEarth q
The author’'s solutions and the tester’s solution’s complexity are different. Its O(8len) for the first solution and o(4len) for the second.
I am talking about the last line of the explanation , that is , even before the authors soln starts.
If you cant find it , search this - “The time complexity of the above function will then be O(lenx4)”. Should it be not O(len48), instead if O(len*4) ?
Yes thats what am saying, you are checking out the author’s solution which is 8 * len. But the editorial has discussed a solution which is focusing on the tester’s code, hence he has written 4len
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.