Skip to main content

Return to Question

added 419 characters in body
Source Link
Ahmed Ismail
Ahmed Ismail
  • 113
  • 1
  • 8

In Gayle Laakman's book "Cracking the Coding Interview", chapter VI (Big O), example 12, the problem states that given the following Java code for computing a string's permutations, it is required to compute the code's complexity

public static void permutation(String str) { permutation(str, ""); } public static void permutation(String str, String prefix) { if (str.length() == 0) { System.out.println(prefix); } else { for (int i = 0; i < str.length(); i++) { String rem = str.substring(0, i) + str.substring(i + 1); permutation(rem, prefix + str.charAt(i)); } } }

The book assumes that since there will be n! permutations, if we consider each of the permutations to be a leaf in the call tree, where each of the leaves is attached to a path of length n, then there will be no more that n*n! nodes in the tree (i.e.: the number of calls is no more than n*n!).

But shouldn't the number of nodes be:

sum(i!), where i = 1 to n?foo+bar

since the number of calls is equivalent to the number of nodes (take a look at the figure in the video Permutations Of String | Code Tutorial by Quinston Pimenta).

If we follow this method, the number of nodes will be 1 (for the first level/root of the tree) + 3 (for the second level) + 32 (for the third level) + 32*1 (for the fourth/bottom level)

i.e.: the number of nodes = 3!/3! + 3!/2! + 3!/1! + 3!/0! = 16

However, according to the aforementioned method, the number of nodes will be 3*3! = 18

Shouldn't we count shared nodes in the tree as one node, since they express one function call?

In Gayle Laakman's book "Cracking the Coding Interview", chapter VI (Big O), example 12, the problem states that given the following Java code for computing a string's permutations, it is required to compute the code's complexity

public static void permutation(String str) { permutation(str, ""); } public static void permutation(String str, String prefix) { if (str.length() == 0) { System.out.println(prefix); } else { for (int i = 0; i < str.length(); i++) { String rem = str.substring(0, i) + str.substring(i + 1); permutation(rem, prefix + str.charAt(i)); } } }

The book assumes that since there will be n! permutations, if we consider each of the permutations to be a leaf in the call tree, where each of the leaves is attached to a path of length n, then there will be no more that n*n! nodes in the tree (i.e.: the number of calls is no more than n*n!).

But shouldn't the number of nodes be:

sum(i!), where i = 1 to n?

since the number of calls is equivalent to the number of nodes (take a look at the figure in the video Permutations Of String | Code Tutorial by Quinston Pimenta).

i.e.: Shouldn't we count shared nodes in the tree as one node, since they express one function call?

In Gayle Laakman's book "Cracking the Coding Interview", chapter VI (Big O), example 12, the problem states that given the following Java code for computing a string's permutations, it is required to compute the code's complexity

public static void permutation(String str) { permutation(str, ""); } public static void permutation(String str, String prefix) { if (str.length() == 0) { System.out.println(prefix); } else { for (int i = 0; i < str.length(); i++) { String rem = str.substring(0, i) + str.substring(i + 1); permutation(rem, prefix + str.charAt(i)); } } }

The book assumes that since there will be n! permutations, if we consider each of the permutations to be a leaf in the call tree, where each of the leaves is attached to a path of length n, then there will be no more that n*n! nodes in the tree (i.e.: the number of calls is no more than n*n!).

But shouldn't the number of nodes be:

foo+bar

since the number of calls is equivalent to the number of nodes (take a look at the figure in the video Permutations Of String | Code Tutorial by Quinston Pimenta).

If we follow this method, the number of nodes will be 1 (for the first level/root of the tree) + 3 (for the second level) + 32 (for the third level) + 32*1 (for the fourth/bottom level)

i.e.: the number of nodes = 3!/3! + 3!/2! + 3!/1! + 3!/0! = 16

However, according to the aforementioned method, the number of nodes will be 3*3! = 18

Shouldn't we count shared nodes in the tree as one node, since they express one function call?

Source Link
Ahmed Ismail
Ahmed Ismail
  • 113
  • 1
  • 8

Counting all permutations of a string (Cracking the Coding Interview, Chapter VI - Example 12)

In Gayle Laakman's book "Cracking the Coding Interview", chapter VI (Big O), example 12, the problem states that given the following Java code for computing a string's permutations, it is required to compute the code's complexity

public static void permutation(String str) { permutation(str, ""); } public static void permutation(String str, String prefix) { if (str.length() == 0) { System.out.println(prefix); } else { for (int i = 0; i < str.length(); i++) { String rem = str.substring(0, i) + str.substring(i + 1); permutation(rem, prefix + str.charAt(i)); } } }

The book assumes that since there will be n! permutations, if we consider each of the permutations to be a leaf in the call tree, where each of the leaves is attached to a path of length n, then there will be no more that n*n! nodes in the tree (i.e.: the number of calls is no more than n*n!).

But shouldn't the number of nodes be:

sum(i!), where i = 1 to n?

since the number of calls is equivalent to the number of nodes (take a look at the figure in the video Permutations Of String | Code Tutorial by Quinston Pimenta).

i.e.: Shouldn't we count shared nodes in the tree as one node, since they express one function call?