I have started doing LC and i was wondering the Time complexity of the code. According to GPT its N^2 But I am not convinced feels more like N^3. As in the loop it’s making the recursive call again. So N recursive call outer than N for Loop and N for recursive call in Loop Anyone can help? Chat GPT analysis: Let’s analyze the time complexity of the provided solution: • The function find is called recursively for each position in the prices array. • Within each recursive call, there is a loop that iterates up to times, where is the length of the prices array. • The number of recursive calls is bounded by the length of the prices array. • Memoization is used to store and retrieve the results of subproblems, ensuring that each subproblem is solved only once. Considering these factors: • The recursion explores all possible combinations of buying and selling stocks, leading to recursive calls. • Within each recursive call, the loop iterates up to times. • Memoization ensures that each subproblem is solved only once, reducing the overall number of computations. Therefore, the overall time complexity of the solution is N^2, where N is the length of the prices array. This is because the recursion explores all possible combinations, and the loop within each recursive call iterates up to N times, resulting in quadratic time complexity.
If you need a tool to find time complexity, you shouldn’t be interviewing for SWE roles.
I need to verify if that’s correct. I used GPT I am leaning thanks tho
You can absolutely write good code without knowing how to calculate time complexity. Design is more art than science. But maybe the interviewer won't get it so you may want to skip the swe role
"Feels more like N^3". You should try to at the very least give a justification...
Added
I think GPT is correct
It’s N^2. You don’t need ChatGPT for such things.
But I why we are not taking the recursive call in the loop as constant? I don’t understand that part will it not account for another N calls? All this seems confusing 😅
Like someone else said it boils down to: F(n) = F(n-1) + n F(n) = F(n-2) + n+ n . . . F(n) = O(1) + n + n + n…. (n times) As you drill down the tree, you will realize it has a depth of n and each level has a worst case time complexity of O(n). So the entire setup will have O(n*n) or O(n^2) complexity. FWIW the problem can be solved in linear time.
I was wondering the exact same thing.