title: Time complexity of algorithm to find all possible words of phone digits
body: <p>I am studying this problem. </p>
  
  <p><a href="http://www.geeksforgeeks.org/find-possible-words-phone-digits/" rel="nofollow">http://www.geeksforgeeks.org/find-possible-words-phone-digits/</a></p>
  
  <p>According to me the time complexity should be O(n^2) but it's mentioned there that time complexity for their algo is O(4^n) Why is it 4^n?</p>
  
  <p>What would be the space complexity? </p>