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++)

    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(N2)

    2. O(N4)

    3. O(log N)

    4. O(3N)