CPSC 170 PreLab 3

1. Find both the number of steps required and the big-Oh complexity of each piece of code below. Show your work!

   1. for (int i=N; i>0; i--)
        for (int j=0; j<N; j++)
          print (j);
      

      
      
      

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

      
      
      

   3. for (int i=N; i>1; i/=2)
          print (i);
      

      
      
      

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

      
      
      

   5. for (int i=0; i<N+3; i++)
        for (int j=0; j<N-4; j++)
          for (int k=0; k<N/2; k++)
            print (k);
      

   
   
   

2. For each complexity below, show what happens to the runtime when the input size doubles. Show your work!
   1. O(N²)

      
      
      

   2. O(N⁴)

      
      
      

   3. O(log N)

      
      
      

   4. O(3^N)