How to calculate the worst case complexity?

  • 0

    Complexity seems to be O(4^15) where 4 represents 4 buckets and 15 is the max length of array. This is calculated based on logic that each stick can go to any edge.
    I understand that by taking desc order sorted array, we are eliminating the negative cases pretty early and hence actual complexity is much lower than this, but how to mathematically calculate and arrive at worst case complexity? I stopped myself from solving it by DFS, thinking that it might run out of time, only to later find in discussion that this is the solution, So, my major concern is how to make sure that the obvious solution will be time bound in cases, where it is hard to calculate the actual complexity.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.