this question could also have been solved with iterative solution with lesser time complexity
but why are doing the recursive solution even though its time complexity is high.
Why iterative solution not considered
hello @Parmeet-Kalsi-1631789033630118
time complexity of both the solution is same . O(n+m).
yeah iterative solution is efficient in terms of space complexity.
iterative approach space complexity-> O(1)
recursive approach space complexity-> O(n+m). // system stack
you can try iterative as well , that is also easy .
Please explain about the time complexity in case of recursive approach
ok,
see we have one list of side n and another list of size m.
now what our merge function is doing.
it is taking approariate node as head and then call the same function on remaining nodes.
so if i represent in terms of state.
T(n+m) = 1+ T(n+m-1)
initailly we had n+m nodes to merge then we picked one node and after that we are left with n+m-1 nodes.
on solving this u will get O(n+m) is time complexity
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.