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(2^{n}), 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?