Big-Oh Analysis Lab

Introduction

Practice the computation of \(\mathcal{O}\) from source code.

Problem 1

To determine the number of steps, count all assignments to sum.

public static int someFunc1(int[] numbers) {
    int sum = 0;

    for (int num : numbers) {
      sum += num;
      for (int i = 0; i < 20; i++) {
        sum += i;
      }
    }
    return sum;
  }

Answer these questions:

1. Is there a different between worse-case and every-case?
2. State the exact growth function
3. proof its membership into its complexity class.

Problem 2

To determine the number of steps, count all assignments to sum.

public static int fun(int[] numbers) {
    int sum = 0;

    for (int i = 0; i < numbers.length; i++) {
      sum += numbers[i];
      for (int j = i; j < numbers.length; j++) {
        sum += numbers[i] * numbers[j];
      }
    }
    return sum;
  }

Answer these questions:

1. Is there a different between worse-case and every-case?
2. State the exact growth function
3. proof its membership into its complexity class.

Problem 3

To determine the number of steps, count all assignments to s.

PROCEDURE DoStuff(numbers1, numbers2)
    s <- 0
    
    FOR x IN numbers1 DO
      FOR y IN numbers2 DO
         IF x < y DO
           RETURN 0
         ELSE
           s <- s + x
         ENDIF
       ENDFOR
    ENDFOR
    
    FOR x IN numbers2 DO
      s <- s + x
    ENDFOR
    
    RETURN s

Answer these questions:

1. Is there a different between worse-case and every-case?
2. How should the input size be represented?
3. State the exact growth function
4. proof its membership into its complexity class.

Problem 4

Consider the following code:

public static int fun3(ArrayList<Integer> nums1, ArrayList<Integer> nums2) {

    int overlap = 0;
    for (int num : nums1) {
      if (nums2.contains(num)) {
        overlap++;
      }
    }
    return overlap;
  }

Answer the following questions:

1. State what is an appropriate basic operation that you will be using to count the number of steps.
2. State the exact growth function
3. proof its membership into its complexity class.

Problem 5

Use incrementing sum as the basic operation. For the sake of simplicity, you may assume that the length of numbers is a power of 2.

public static int fun4(int[] numbers) {
    int sum = 0;
    for (int i = numbers.length - 1; i >= 1; i /= 2) {
      for (int j = 0; j < numbers.length / 2; j++) {
        sum++;
      }
    }
    return sum;
  }

Answer the following questions:

1. Is there a different between worse-case and every-case?
2. State the exact growth function
3. proof its membership into its complexity class.

Problem 6

public static int fun5(int[] numbers) {
    int sum = 0;
    for (int i = 0; i < numbers.length; i++) {
        flibbert(numbers); // We know that flibbert requires fewer than
                           // n^2 operations in the worst case. 
    }
    return sum;
  }

Answer the following questions:

1. Is there a different between worse-case and every-case?
2. State the exact growth function
3. proof its membership into its complexity class.

Lab Submission

If you are in class, there is nothing to submit (its a participation grade). If you are not in class, you must submit a scanned sheet with the answers to the 6 questions by the due date.