What is the time complexity for problem 6.22?

#1

Hi there,

The algorithm of Phone Number Mnemonic is exhaustive recursion: enumerate each character in the given string num and recursively append other letters to it. I’m not so sure what is the time complexity of it?

I think for exhaustive recursion, such as N Queens and Power Set, the time complexity is exponential. Same like this one, T(n) = m * T(n - 1) + c, where m is the number of letters and n is the length of the given string. So the time complexity is T(n) = O(m ^ n) . Is it correct?

Thanks a lot.

0 Likes
#2

Hey Carl,

You are right, the time complexity is exponential indeed. In this problem, we can treat m = 4. As a result, the time complexity is O(4^n).

Please feel to let us know if you have any problem.

0 Likes