CS 201 Assignment: Computational Complexity

This assignment is to be done individually. You can share ideas and thoughts with other people in the class, but you should write up your own assignment.

Submit your assignment electronically. If you want to write it out on paper, which is likely the easiest way to do it, scan your solution using any of the scanners in the library or elsewhere, and submit. If you prefer, you may also do it using Word or OpenOffice (yechhh, but they work) or learn LaTeX, which lets you produce gorgeously readable mathematical text like this (skip to the third page).

1. Determine how many times the output statement is displayed in each of the following fragments. Indicate whether the number of times that the output is printed is better described as O(n) or O(n²).

   // example a
   for (int i=0; i < n; i++)
   {
       for (int j=0; j < n; j++)
       {
           System.out.println(i + " " + j);
       }
   }
   
   // example b
   for (int i=0; i < n; i++)
   {
       for (int j=0; j < 2; j++)
       {
           System.out.println(i + " " + j);
       }
   }
   
   
   // example c
   for (int i=0; i < n; i++)
   {
       for (int j=n-1; j >=0; j--)
       {
           System.out.println(i + " " + j);
       }
   }
   
   
   // example d
   for (int i=0; i < n; i++)
   {
       for (int j=0; j < i; j++)
       {
           if (j & i == 0)
           {
               System.out.println(i + " " + j);
           }
       }
   }
   

2. For T(n) = n³ - 5n² + 20n - 10, find values of n₀ and c such that cn³ is larger than T(n) for all n larger than or equal to n₀.
3. Show that n² is O(n³) by using the definition of big-O.
4. Show that n³ is not O(n²) by using the definition of big-O.