Complexity Exercises


Try the following exercises. They all deal with complexity issues and will help you to a better understanding of the lecture material.
 

Question 1

An algorithm takes 0.5 ms for input size 100. How long will it take for input size 500 if the running time is the following:
 

  1. linear
  2. 0(N lg N)
  3. quadratic
  4. cubic


Question 2

An algorithm takes 0.5 ms for input size 100. How large a problem can be solved in 1 minute if the running time is the following:
 

  1. linear
  2. 0(N lg N)
  3. quadratic
  4. cubic


Question 3

Order the following functions by growth rate: N, N1/2, (N)1.5,  N2, N lg N, N lg lg N, N lg2 N, N lg (N2), 2/N, 2N, 2 N/2, 37, N3, N2 lg N. Group the functions into complexity classes.

Question 4

For each of the following program fragments, do the following
 

  1. Give a Big-Oh analysis of the running time.
  2. Implement the code and run for several values of N.
  3. Compare you analysis with the actual running times.
for (int i = 0; i < n; i++)
   sum++;
 

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

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

for (int i = 0; i < n; i++)
   for (int j = 0; j < n * n; j++)
      sum++;
 

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

(This is a hard one)
for (int i = 0; i < n; i++)
   for (int j = 0; j < n * n; j++)
      for (int k = 0; k < j; k++)
         sum++;
 

(This is a hard one)
for (int i = 0; i < n; i++)
   for (int j = 0; j < i * i; j++)
      if (j % i == 0)
      for (int k = 0; k < j; k++)
         sum++;


Question 5

Prove by induction: