This first assignment is an analysis of algorithms and understanding growth functions using Big-Oh notation.
1.Explain what O(1) means.
2.If the Big-O calculation for a code segment is O(2n), what do you conclude about the code segment? Why?
3.How many times will the following code print out Hello World (in terms of the length of the array)?
for(int i = 0; i < array.length; i++) {
for(int j = 0; j < array.length; j++) {
for(int k = 0; k < array.length; k++) {
System.out.println(“Hello World!”);
}
}
}
4.What is the complexity of the following code (in terms of the length of the array), assuming someMethod has a complexity of O(1)?
for(int i = 0; i < array.length; i++)
for(int j = 0; j < array.length; j++)
someMethod(array[j]);
5.What is the complexity of the following code (in terms of the length of the array)?
for(int i = 0; i < 5; i++)
System.out.println(array[i]);
6.Why do we do algorithm analysis to compare algorithms?
7.Write a code segment that represents an order, for each of the following orders.
Log N
N
N Log N
N
N^2
N^3
2^N
8.How can we be certain (validate) that the code segments in the previous question are the correct order?
