You can hand write these answers but draw a horizontal line between every problem to clearly separate the problems. Include the problem number in each case.

1.Show using the definition that 8n+2 is in O(n)

2. Show using the definition that 2N^{2}+n is in O(n^{2})

3. In terms of n, how many times does the assignment statement execute? What is the complexity of this code segment?

for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) x=x+i+j;

4. Consider the series 3+ 6+9+12 +…+ 153. If 3 is the first term, 6 the second, what term is 153?

5. What is the sum of the series in question 4?

6. Here is a series. 12 + 4 +4/3+ 4/9 …. What type of series is it? What is the upper limit for its sum?

7. What power could I raise 3 to in order to obtain 2.6? How could we do this in C++. Give a c++ code segment to do this. Test it in visual studio.

8. Suppose that we start with N=1,000,000 int values in an unsorted array. What is the complexity of searching for a specific value in this array? What if the array is sorted? Explain.

9. Order these complexities from small to large , 2^{N} , N^{N} , N! ?

10. How many base 10 digits can be stored in a 32 bit integer? 64bit? Give the mathematics for N bits.