Time complexity of a tree-based algorithm

Question

I solved a practice interview problem that was sent me by Daily Coding Problem mailing list. I am now curious about the exact time complexity of my solution.

Problem Statement

Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded.

For example, the message '111' would give 3, since it could be decoded as 'aaa', 'ka', and 'ak'. You can assume that the messages are decodable. For example, '001' is not allowed.

I made an assumption that my solution should accept any type of mapping, not just the one mentioned in the question. So the running time of the algorithm is parametrized by the encoded message length and the type of mapping used.

Attempted Solution

class Node:

    def __init__(self, val):
        self.val = val
        self.children = []

    def add_child(self, child):
        self.children.append(child)


def count_encodings(cipher, mapping):
    # what is the longest possible map value
    longest_val = max([len(str(x)) for x in mapping.values()])
    root = Node('')
    create_cipher_subtree(root, cipher, longest_val, mapping)
    return count_leaves(root)

def create_cipher_subtree(node, cipher, longest_val, mapping):
    for part_len in range(1, min(longest_val, len(cipher)) + 1):
        curr_part = cipher[:part_len]
        if curr_part in mapping.values():
            child = Node(curr_part)
            node.add_child(child)
            remaining_part = cipher[part_len:]
            if remaining_part:
                create_cipher_subtree(child, remaining_part, longest_val, mapping)

def count_leaves(node):
    if not node.children:
        return 1
    count = 0
    for child in node.children:
        count += count_leaves(child)
    return count

We can then reproduce the example solution as follows:

from string import ascii_lowercase
mapping = {k: str(v) for v, k in enumerate(ascii_lowercase)}
cipher = '111'
print(count_encodings(cipher, mapping))

In short, this solution constructs a tree, like this:

            ''
       '1'     '11'
    '1'  '11'     '1'
 '1' 

Then the number of leaf nodes is counted.

Explanation

First, the algorithm checks all possible values in the mapping and records the length of the longest value (longest_val).

We then create a tree, where each node's val field is a part of the encoded message (cipher) that corresponds to a single mapping value; the root is the only node which has val as empty string. Concatenation of nodes' val fields along the path from the root to a leaf is one possible way of encoding.

The tree is created as follows:

1. Check if the first character of cipher can be interpreted as a mapping value.
2. If yes, create a node with that value recorded and make it a child of root. Then, pass the rest of the remaining_part of the encoded message (everything past the first character) to the child and repeat the process from there.
3. Check if the first two characters of cipher can be interpreted as a mapping value.
4. Repeat step 2, but now val is two characters. The remaining_part would be everything in the encoded message past the first two values. This would create another child node of root.
5. If longest_val was 3, we would then check if the first 3 characters of cipher can be interpreted as a mapping value.... And so on.

After the tree is created, we count the number of leaf nodes, which corresponds to number of possible messages that can produce the provided encoding.

Complexity Analysis

I know that creating the tree of all possible ways the message could have been encoded might have been an overkill for this problem (in terms of space use), but doing it this way helped me better reason about the solution.

I am now unsure about the exact relation between a mapping choice and message length, and the answer to the question. What is the time complexity of this solution?

I am more interested in how various mappings affect the complexity. E.g. if some of the values in the mapping were 3-digit numbers, then many nodes in the tree would have 3 children. Does this increase the complexity of the algorithm? How would one capture this fact when writing Big-Oh expression for the algorithm?

Answer 1

You can show a simple exponential lower bound for you algorithm as follows.

1. Assume we have a $d$ digit encoding (2 in your initial example).
2. For any cipher text of length $n$ we can create a worst-case encoding of $n$ 1's.
3. Now we divide the input into $n \ / \ d$ segments of length $d$.
4. For any of these segments, we have $2^{d-1}$ ways of decoding it.
   • Take $d = 4$ for example, with a segment "1111" we have the following decodings:
     1. "1111"
     2. "1", "111"
     3. "1", "1", "11"
     4. "1", "1", "1", "1"
     5. "1", "11", "1"
     6. "11", "11"
     7. "11", "1", "1"
     8. "111", "1"
5. Now we can decode all of these $n \ / \ d$ segments separately so we can multiply this together to get:

$$(2^{d-1})^{n/d} = 2^{(d-1)n/d}$$

---

You can get a tighter bound for this however by noting that the number of decodings for a string of ones is:

$$f(n) = \begin{cases} 1 & n = 1\\ 2 & n = 2\\ \vdots & \vdots\\ 2^{d-1} & n = d\\ \sum_{i = 1}^d f(n - i) \end{cases}$$

If we plug in for $d=2$ we actually see something familiar: $$f(n) = \begin{cases} 1 & n = 1\\ 2 & n = 2\\ f(n-1) + f(n-2) \end{cases}$$ This is the Fibonacci Sequence! This, we know is exponential in $n$. If you try $d=3$ you get the Tribonnaci Sequence. As you increase $d$ you simply get higher order Fibonacci sequences. All of these will be exponential in the worst case.