Processing math: 100%
CS 240: Algorithms and Data Structures
James Madison University, Fall 2017

For each of the methods below:

Listing 1

Count all arithmetic operations.

  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;
  }

Listing 2

Count all arithmetic operations.

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

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

  }

Listing 3

Count all arithmetic operations.

  public static int fun1(int[] numbers1, int[] numbers2) {
    int sum = 0;

    for (int i = 0; i < numbers1.length; i++) {
      for (int j = i; j < numbers1.length; j++) {
        if (numbers1[i] < numbers1[j]) {
          return 0;
        } else {
          sum += numbers1[i];
        }
      }
    }

    for (int i = 0; i < numbers2.length; i++) {
      sum += numbers2[i];
    }

    return sum;
  }

Listing 4

Count all arithmetic operations.

  public static int fun2(String sentence) {

    int[] counts = new int[sentence.length()];

    for (int i = 0; i < sentence.length(); i++) {
      for (int j = i; j < sentence.length(); j++) {
        if (sentence.charAt(i) == sentence.charAt(j)) {
          counts[i] += 1;
        }
      }
    }

    int howMany = 0;
    for (int count : counts) {
      if (count > 1) {
        howMany++;
      }
    }
    return howMany;
  }

Listing 5

Select an appropriate basic operation.

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

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

Listing 6

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;
  }

Listing 7

   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;
  }