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 2N2+n is in O(n2)
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 , 2N , NN , N! ?
10. How many base 10 digits can be stored in a 32 bit integer? 64bit? Give the mathematics for N bits.