how to find the time and space complexity in this case?
CPP - Recursion - Phone Keypad
hey @Subham2107, time complexity will be O(4^n). Some number represent 3 symbols (like 2 has abc) and some number represent 4 symbols (like 9 has wxyz). In the worst case we can say max 4 symbols in one digit.
Now if we have 2 digit number, for first digit has 4 symbols and for for second digit has 4 symbols.
For each symbol of first digit we can use any one out of 4 symbols of second digit. (4 combinations)
As there are 4 symbols in first number we will be having 16 combinations. Which is nothing but 4^2=16.
So time complexity is O(4^n).
Coming to space complexity, As extra space is generated is only for digit varaible, it will be O(depth of recursive tree X 1)= O(depth of recursive tree).
Now build the on your own and find the depth.
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.