CPSC 170 Spring 2004
Computational 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);