Time complexity of Letter Combinations of a Phone Number

Question

Here is LeetCode question 17:

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

(https://leetcode.com/problems/letter-combinations-of-a-phone-number/)

Below is my DFS recursive code:

class Solution {
    public static final String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    
    public List<String> letterCombinations(String digits){
        List<String> result = new ArrayList<String>();
        if(digits == null || digits.length() == 0){return result;}
        
        
    
        int curr_index = 0;
        StringBuilder prefix = new StringBuilder("");
        
        update_result(digits, prefix, curr_index, result);
    
        return result;
        
    
    }

    private void update_result(String digits, StringBuilder prefix, int curr_index, List<String> result){
        if(curr_index >= digits.length()){
            result.add(prefix.toString());
            return;
        }
        else{
            String letters = map[ digits.charAt(curr_index) - '0' ];
            for(int i = 0; i < letters.length(); i++){
                prefix.append( letters.charAt(i) );
                update_result(digits, prefix, curr_index+1, result);
                prefix.deleteCharAt(prefix.length() -1);
            }
            return;
        }
        
    }

}

In the LeetCode solutions, it says the time complexity is O(n*n^4), where n is the length of the input. I have trouble understanding except the n^4, where the remaining extra n comes from.

My analysis of my code is: T(n) = O(1) + 4T(n-1). (The for loop is repeated for 4 times which length decremented by 1. And in the loop constant time is required for update the prefix String.)

It solves to 1 + 4 + 4^1+ ... + 4^n = O(4^n)

Can anyone help with why the solution says the time complexity is O(n*4^n)?

Answer 1

I agree with you, the time complexity should be O(4^n).

I have several ideas why it can be O(n * 4^n):

1. StringBuilder's append method can take O(n) time when its capacity reaches threshold, which means copying all elements to a new array. But in your case maximum length of the resulting string is 4 (from the problem constraints), whereas the default value of the threshold is 16 (https://docs.oracle.com/javase/8/docs/api/java/lang/StringBuilder.html#StringBuilder-java.lang.String-). Since 4 < 16, it always takes O(1) time.

2. StringBuilder's deleteCharAt method takes O(n) time in worst case, because of array copy. But in your case, you are removing only last character, which takes O(1) time.

3. Used String instead of StringBuilder, where concatenation and deletion with one element takes O(n) time

Answer 2

Its because the width of the tree is O(4^n) and the height of the tree is O(n). Watch this video for a better explanation than I can give: https://www.youtube.com/watch?v=0snEunUacZY