Will the time complexity of the Recursive solution of the Wines Problem is O(2^n) where is the n is the number of wines bottle. Please confirm and also explain how the time complexity of the top down approach is O(n^2).
Time Complexity for Wine Problem
hello @Sakshi2004
yeah.
yeah it is O(n^2) .
we will have atmost n^2 unique states(pair of start,end) and at every state we are perfoming O(1) work (i,e we are either picking left or right and moving to new state) .
so we can write net total complexity = number of unique states x transition time from one state to other state
= O(N^2 * 1)= o(N^2)
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.