BigO Flashcards
Which of the following are equivalent to O(N) and why? A.) O(N+P), where P smaller than N/2 B.) O(2N) C.) O(N + logN) D.) O(N+M)
A,B,C
A – if P is smaller than N/2 than N is the dominant. we can drop the other
B – we drop constant, so O(2N) is O(N)
C – O(N) dominates O(logN) so we can drop O(logN)
D – we don’t know the relationship between N and M, so we have to keep both
What is the time complexity of this method and why?
boolean isPrime(int n){
for(int x = 2; x*x <= n; x++){
if(n%x==0){
return false;
}
}
return true;
}O(square root n)
the for loop start at 2 and end when x*x equals n. Therefore x^2=N, so x equals square root N
What is the runtime of this and why?
Sum the values of all the nodes in a balanced BST:
int sum(Node node){
if(node == null){
return 0;
}
return sum(node.left) + node.value + sum(node.right);
}
O(N)
Touches each node and does constant amount of work so it is O(N)
Also because it is a recursive pattern we can use the O(branches^depth) calculation. It has two branches so O(2^depth). Depth with a balanced BST is logN, so it is O(2^logN).
Since we know that
b^c = a is also log(based b)a = c
2^logN = x is also log(based 2)x = log(based 2)N
which means x=N, so the answer is O(N)
What would be the runtime of this and why?
An algorithm takes an array of strings, sorts each string and then sorts array.
O(A*S(logA + logS))
If S is the length of the longest string and A is the length of the array.
sorting one string is –> O(S logS) (with e.g.: merge sort)
doing this for all strings is (A many strings) –> O(A*S logS)
Sorting strings requires comparison:
- each comparison takes O(S) time
- the sorting requires O(A logA) comparisons
- for each comparisons it is O(A*S logA) time
add this together is O(A*S(logA + logS))
What is the time complexity and why?
void printUnorderedPairs(int[] array){
for(int i = 0; i< array.length; i++){
for(int j= i+1; j < array.length; j++){
System.out.println(array[i] + " " + array[j]);
}
}
}
O(n^2)
if you visualize it with an example on a matrix you can see that it will be half of an N*N matrix, so it is N^2/2 which is N^2 when we drop the constant.
What is the insertion runtime of an ArrayList and why?
O(1)
In some cases when you insert an element the size of the array is not enough. In this case a new array is created (in java the new array will have double the size of the original) and the elements are copied over. This means that the final time we copy over N/2 elements, before that it was N/4, before that it was N/8. So it is N/2+N/4+N/8 … +2+1. Which is almost N. So one insertion takes O(1) time.
What is a runtime of concatenating strings together like this? and why?
String joinWords(String[] words) {
String sentence = "";
for (String w: words) {
sentence = sentence + w;
}
return sentence;
}O(x*n^2) where x is the length of the string you concatenate to the end, and there are n strings.
On each concatenation a new string is created and the original and the new string is copied over character by character. The first iteration requires to copy x characters, the second 2x characters. This copying happens 1+2+….+n times, which is n(n+1)/2.
(if n=8, we have 4 pairs of 9, because 1+2+3+4+5+6+7+8 leads to (1+8)+(2+7)+(3+6)+(4+5))
O(n(n+1)/2) equals to O(n^2) because we drop the constants
What is the time complexity of the Rabin-Karp Algorithm?
best and average O(n+m) where n is the length of the pattern and m is the length of the text
worst case is O(n*m)
What is the time complexity of inserting and removing from a queue or stack?
O(1)
What is the time complexity of inserting a node to a binary search tree?
O(h) where h is the height of the tree
if it is a balanced tree than O(logN) if not it’s O(n)
What is the time and space complexity of a trie?
Insert and search costs O(key_length) time, however the memory requirements of Trie is O(ALPHABET_SIZE * key_length * N) where N is number of keys in Trie.
What is the time complexity of bubble sort?
O(n^2)
What is the time complexity of selection sort?
O(n^2)
What is the time complexity of counting sort?
O(n+k) where n is the number of elements in input array and k is the range of input.
What is the time complexity of Radix sort?
O(n*d), where n is the size of the array and d is the number of digits in the largest number.
