Why is the time complexity of this example from "Cracking the Coding Interview" O(k c^k)?

user_5816638 0
Viewed 2143

This question is from Cracking the Coding Interview 6th Edition, Question V1.11.

The following code prints all strings of length k where the characters are in sorted order. It does this by generating all strings of length k and then checking if each is sorted. What is the runtime?

package QVI_11_Print_Sorted_Strings;


public class Question {

    public static int numChars = 26;

    public static void printSortedStrings(int remaining) {
        printSortedStrings(remaining, "");
    }

    public static void printSortedStrings(int remaining, String prefix) {
        if (remaining == 0) {
            if (isInOrder(prefix)) {
                System.out.println(prefix);
            }
        } else {
            for (int i = 0; i < numChars; i++) {
                char c = ithLetter(i);
                printSortedStrings(remaining - 1, prefix + c);
            }
        }
    }

    public static boolean isInOrder(String s) {
        for (int i = 1; i < s.length(); i++) {
            int prev = ithLetter(s.charAt(i - 1));
            int curr = ithLetter(s.charAt(i));
            if (prev > curr) {
                return false;
            }
        }
        return true;
    }

    public static char ithLetter(int i) {
        return (char) (((int) 'a') + i);
    }

    public static void main(String[] args) {
        printSortedStrings(5);
    }

}

The answer is O(k c^k) where k is the length of the string and c is the number of characters in the alphabet. It takes O(c^k) time to generate each string. Then, we need to check that each of these is sorted, which takes O(k) time.

Now, I understand where O(k) comes from but I don't see how O(c^k) came about.

recursion big-o algorithm java string
3 Answers

The recursive calls to printSortedStrings form a recursion tree. Because the total number of nodes is about a constant factor of the number of nodes at the lowest level, and the upper levels don't do more work than the lowest level, then only the cost of the lowest level is significant.

Take for example, c being 2, and k being 3:

Looking at the first level of the tree this produces:

2 (or 2^1) strings, "a", "b".

The second level produces:

4 (or 2^2) strings, "aa", "ab", "ba", "bb".

The third level produces:

8 (or 2^3) strings, "aaa", "aab", "aba", "abb", "baa", "bab", "bba", "bbb".

The cost to produce the next string in sequence is linear. The characters from the old string plus the new character are copied into the new string.

This depends on the length of the string, so for the first level the cost is 1, the second level cost is 2, and the third level cost is 3. Multiply by the number of items at each level:

(2^1)*1 + (2^2)*2 + (2^3)*3 = 34

This pattern would continue if k was 4, then it would be:

(2^1)*1 + (2^2)*2 + (2^3)*3 + (2^4)*4 = 98

This thing about sums like this is that the last term is greater than all the previous ones combined. So only the last term is significant:

(2^1)*1 + (2^2)*2 + (2^3)*3 < (2^4)*4

Because:

(2^1)*1 + (2^2)*2 + (2^3)*3
< (2^1)*3 + (2^2)*3 + (2^3)*3
= (2^1 + 2^2 + 2^3) * 3
= (2^4 - 2) * 3
< (2^4 - 2) * 4
< (2^4) * 4

So the whole sum is less than 2*(2^4)*4, or 2*(c^k)*k, or O(k c^k).

At the end of the recursion, there is more linear time work. There are c^k nodes with k work giving another O(k c^k) cost. So the total cost is still O(k c^k).

One other thing is that the for-loop takes linear time per string as well, but this works out to a total of O(k c^k), for similar reasons as above.

user_2980290

I don’t think they accounted for the k^2 in the book because the code isn’t written in Java in the actual book. So it is safe to assume that string concatenation is O(1). Also, the answer explanation in the book is not the best. It only takes O(k) time to generate each string but there are O(c^k) possible strings. And it takes O(k) to verify the result so it should be O(k^2 c^k) not O(kc^k) (with an O(1) string concatenation time). However, that you should discuss with your interviewer, just ask if prints, concatenation, etc. take O(1) time or longer.

user_86609560
Related