Homework#0 Complexity

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.

Comments are closed.