COMPUTING SCIENCE 210
Algorithm Analysis and Data Structures

Big-O and Big-Omega Analysis

Examples and Exercises

Example 1.2, page 19

Use Big-O analysis to determine the time efficiency of the following C++ fragment in terms of the integer n:

   for (k = 0; k < n / 2; ++k)
   {
      .
      .
      .
      for (j = 0; j < n * n;  ++j)
      {
         .
         .
         .
      }
   }

Example 1.3, page 19

Use Big-O analysis to determine the time efficiency of the following C++ fragment in terms of the integer n:

   for (k = 0; k < n / 2; ++k)
   {
      .
      .
      .
   }
   for (j = 0; j < n * n;  ++j)
   {
      .
      .
      .
   }

Example 1.4, page 20

Use Big-O analysis to determine the time efficiency of the following C++ fragment in terms of the integer n:

   k = n;
   while (k > 1)
   {
      .
      .
      .
      k /= 2;
   }

Exercise 1.2.5, page 29

Do Exercise 1.2.5, and compare your answers with those given in Appendix E on page A-13.

Exercise 1.2.8, page 29

Use Big-O analysis to determine the time efficiency of the following C++ fragment in terms of the integer n:

   x = 1;
   do
   {
      y = n;
      while (y > 0)
      {
         . . .
         --y;
      }
      x *= 2;
   }
   while (x < n * n);