Big O Notation and Frequently missed questions

From Craking the Coding Interview 

Example 10:

boolean isPrime(int n) {
	for (int x = 2; x * x <=n; x++){
    	if (n % x == 0){
        	return false;
        }
    }
    return true;
}

In this case, it's easy to miss it like O(n), but because it's doing the for loop until the sqrt(n). 

 

So it looks like x<=sqrt(n).

 

The Big O is O(sqrt(n)).

 

Example 12:

void permutation(String str) {
	permutation(str, "");
}

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));
        }
    }
}

This question is more about "How many times does permutation get called in its base case?"

 

If we were to generate a permutation, then we would need to pick characters for each "slot." Suppose we had 7 characters in the string. In the first slot, we have 7 choices. Once we pick the letter there, we have choices for the next slot. (Note that this is 6 choices for each of the 7 choices earlier.) Then 5 choices for the next slot, and so on. 

 

Therefore, the total number of optionsis 7*6*5*4*3*2*1, which is also expressed as 7! (7 factorial)

 

This tells us that there are n! permutations. Therefore, permutation is called n! times in its base case (when prefix is the full permutation).

 

How many times does permutation get called before its base case?

 

But, of course, we also need to consider how many times lines 9 though 12 are hit. Picture a large call treee representing all the calls. There are n! leaves, as shown above. Each leaf is attached to a path of length n. Therefore, we know there will be no more than n * n! nodes (function calls) in this tree.

 

How long does each function call take?

 

Executing line 7 takes O(n) time since each character needs to be printed.

 

Line 10 and line 11 will also take O(n) time combined, due to the string concatenation. Observe that the sum of the lengths of rem, prefix, and str.charAt(i) wil always be n.

 

Each node in our call tree therefore corresponds to O(n) work.

 

What is the total runtime?

 

Since we are calling permutation O(n * n!) times (as an upper bound) and each one takes O(n) time, the total runtime equationwill not exceed O(n^2 *n!).