what is the space and time complexity of keypad problem?
Time and space complexity?
hey @namangarg31 , 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).
dont forget to mark the doubt resolved and hit like if cleared 