## CPSC 170 Spring 2004Computational Complexity Exercises

Definition of Big Oh: Let f and g be functions mapping nonnegative reals into nonnegative reals. Then f is big-Oh of g, written f=O(g), if there exist positive constants n0 and c such that for x >= n0, f(x) <= c*g(x).
(from Gersting, Mathematical Structures for Computer Science, 4th ed.)

1. Find the big-Oh equivalent for each function below.
1. 3N2

2. 3N2 + 100N + 50

3. N/4

4. (log N)/2

5. log (N/2)

6. 2N/4 + log N + 10

7. 3(N2)(log N) + N + 10

2. In class we showed that 1 + 2 + ... + N-1 = N(N-1)/2 = O(N2).

1. Use the same technique to find a closed form for 4 + 5 + ... + N-2. Then find its big-Oh equivalent.

2. Use the same technique to find a close form for a + (a+1) + (a+2) + ... + (N+b) for arbitrary constants a and b and find its big-Oh equivalent.

3. Use the same technique to find a closed form for a + (a+1) + .. + ... + N/b for arbitrary constants a and b, and find its big-Oh equivalent.

3. Find the big-Oh complexity of each piece of code below.
1. ```for (int i=1; i<N/3; i++)
print(i);

```

2. ```for (int i=0; i<N/3; i++)
print(i);

```

3. ```for (int i=0; i<N; i++)
for (int j=0; j<N; j++
print(i);

```

4. ```for (int i=1; i<N i*=2)
print(i);

```

5. ```for (int i=0; i<N/2; i++)
for (int j=1; j<N+3; j++)
print(i);

```

6. ```for (int i=0; i<10; i++)
print(i);

```

7. ```for (int i=0; i<10; i++)
for (int j=0; j<N/2; j++)
print(i);

```