We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Sorry, just saw your response. I believe it's still O(n^3). Let me try to explain here, hopefully it helps.
The problem is the min function. It in itself is O(n) complexity (albeit the with a very small constant due to it being written in C). It will have to be called every time the lambda object (lambda x: x-min(stick)) is called, and the lambda object is called by inner filter the number of times equal to the size of its second argument, which is stick. So, O(n) times. In total, already O(n^2).
On top of this you have your outer filter call, whose complexity in a similar fashion will be equal to the complexity of its first argument (lambda y : y>0) which is O(1) multiplied by the size of its second argument which is O(n). So, in total still O(n^2).
Finally, on top of all this you have the while loop which iterates O(n) times. So, in total we just achieved O(n^3) complexity. Gotta be careful with these complexity analyses, they can be tricky :)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Cut the sticks
You are viewing a single comment's thread. Return to all comments →
Sorry, just saw your response. I believe it's still O(n^3). Let me try to explain here, hopefully it helps.
The problem is the min function. It in itself is O(n) complexity (albeit the with a very small constant due to it being written in C). It will have to be called every time the lambda object (lambda x: x-min(stick)) is called, and the lambda object is called by inner filter the number of times equal to the size of its second argument, which is stick. So, O(n) times. In total, already O(n^2).
On top of this you have your outer filter call, whose complexity in a similar fashion will be equal to the complexity of its first argument (lambda y : y>0) which is O(1) multiplied by the size of its second argument which is O(n). So, in total still O(n^2).
Finally, on top of all this you have the while loop which iterates O(n) times. So, in total we just achieved O(n^3) complexity. Gotta be careful with these complexity analyses, they can be tricky :)