didnt get why its o(n) for fibonacci series …and o(log n) for quicksort…as these are the number of steps in the recursion… how do they account for the maximum space taken ???
Didnt understand space complexity for recursion
@niketagarwal10 dont get confused between time and space complexity. Time only adds up, but space can be decreased too. For eg in the recursion implementation of fibonacci, the MAX space that can be taken up is O(n) for all the other other calls it is never more than that. So the total space complexity remains O(n).
On the other hand, the time taken for the program to complete execution keeps increasing so it is different for DP and recursive solutions.
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.