Computer Science Flashcards
What is Big O?
It’s the upper bound on the time an algorithm takes to operate.
What is bi Ω?
It is the lower bound on the tome a algorithm takes to operate.
What is big Θ?
An algorithm is Θ(Ν) if it’s both O(N) and Θ(N).
Θ(N) gives a tight bound on runtime. In industry, we use this as O instead.
What is an ArrayList and what is it’s amortized time for adding an element?
It is a dynamically resizing array.
The array copies all it’s elements into a new array when it runs out of space.
The amortized time of adding an item is O(1).
Because amortised it’s O(x+x/2+x/4+x/8+...+1) which is roughly O(2X).
Therefore the amortized time is O(1). ????
What is a Log N runtime?
It is a runtime that takes as many steps as the logarithm of the length of the dataset.
A good example is a binary search. On a data set of 16 elements, it would take up to 4 steps to find an item.
N = 16
N = 8
N = 4
N = 2
N = 1
log 2 16 = 4
Can you describe an O(2^N) runtime?
It can be a recursive runtime that each recursion makes 2 recursive calls.
If such an operation would create nodes in a tree it would make a balanced binary tree so we can actually express this as:
F(1)
F(2) <
F(1)
F(3) <
F(1)
F(2) <
F(1)
F(4) <
F(1)
F(2) <
F(1)
F(3) <
F(1)
F(2) <
F(1)
What is the runtime of
for i in array
for j in array
print(i + j)
O(N^2) Because it prints all possible combinations.
What is the big O of…
void printUnorderedPairs(int[] arrayA, int[] arrayB) {
for (int i = 0; i < arrayA.length; i++) {
for (int j = 0; j < arrayB.length; j++) {
if (arrayA[i] < arrayB[j] ) {
System.out.println(arrayA[i] + "," + arrayB[j]);
}
}
}
}
0(ab) because the iteration is between two different datasets.
What is the big O of…
void printUnorderedPairs(int[] arrayA, int[] arrayB) {
for (int i = 0; i < arrayA.length; i++) {
for (int j = 0; j < arrayB.length; j++) {
for (int k = 0; k < 100000; k++) {
System.out.println(arrayA[i] + "," + arrayB[j]);
}
}
}
}
O(ab) because the third loop is constant time.
What is the big O of…
void reverse(int [] array) {
for (int i = 0; i < array.length / 2; i++) {
int other = array.length - i -1;
int temp = array[i];
array[i] = array[other];
array[other] = temp;
}
}
0(N)!
The fact that it only goes through the array(in terms of iterations) does not impact the big O time.
Is O(N + P) where P < N/2 equivalent to O(N)?
Yes,
if P < n/2, then we know that N is the dominant term, so we can drop the O(P).
Is O(2N) equivalent to O(N)?
Yes,
since we drop constants.
Is O(N + log N) equivalent to O(N)?
Yes,
O(N) dominates O(log N), so we can drop the O(log N).
Is O(N + M) equivalent to O(N)?
No,
because there is no established relationship between N and M, so, we have to keep both values.
Suppose we had an algorithm that:
- took an array of strings
- sorted each string
- then sorted the full array
What would the runtime be?
It is O(a*s(log a + log s)).
- let s be the length of the longest string.
- let a be the length of the array.
- Sorting each string is O(s log s). We have to do this for every string(and there are a number of strings), so that’s O(a * s log s),
- We have to sort all the strings because we have to compare the pairs that operation is O(a*s log a)
- If you add up this two parts, you get
O(a*s(log a + log s))
This is it, There is no way to reduce it further.
This code prints the permutations of a string.
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.subsstring(0, i) + str.substring(i + 1);
permutation(rem, prefix + str.charAt(i));
}
}
}
~~~
~~~
it is O(n!)
