[Big O] Missed Questions

From Cracking the Coding Interview:

Question 10:

int sumDigits(int n) {
	int sum = 0;
    while (n < 0) {
    	num += n % 10;
        n /= 10;
    }
    return sum;
}

The runtime will be the number of digits in the number. A number with d digits can have a value up to 10^d. if n = 10^d, then d = log n. Therefore, the runtime is 0(log n).

 

Question 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 its runtime?

int numChars = 26;

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

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

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

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

The answer is O(kc^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.

 

Question 12: The following code computes the intersection (the number of elements in common) of two arrays. It assumes that neither array has duplicates. It computes the intersection by sorting one array (array b) and then iterating through array a checking (via binary search) if each value is in b. What is its runtime?

int intersection(int[] a, int[] b) {
	mergesort(b);
    int intersect = 0;
    
    for(int x:a) {
    	if (binarySearch(b, x) >= 0){
        	intersect++;
        }
    }
    
    return intersect;
 }

The answer is O(b lob b + a log b). First, we have to sort array b, which takes O(b log b) time (mergesort). Then, for each element in a , we do binary search in O(log b) time. The second part takes O(a log b) time (O(n) for loop and O(log b) for binary search)