CMPS 144L Lab Activity
Time/Space used by Recursive Array Summing

Download the Java class ArraySummer. It has two methods named segSumA(). The second one, which is recursive, computes the sum of the elements in a specified segment of an array of integers. (The first one does the same thing with respect to a complete array —which is a special case of an array segment— and thus simply calls the second one.)

The logic employed is based upon the observation (as discussed in lecture) that the sum of the elements in the array segment a[low..high) is

  1. zero, if the array segment is empty (i.e., low = high), and
  2. otherwise, obtained by adding its first element, a[low], to the sum of the elements in a[low+1..high).

The class is "instrumented" to keep track of how many recursive calls were made and the maximum recursion depth reached. (The private methods entering() and leaving(), which update the instance variables callCntr, callDepth, and maxCallDepth, are used for this purpose.)

The class has a main() method that invites the user to create an array of a specified length, following which it computes the sum of the array's elements and gives a "report" of the results. (This repeats until the user enters a negative number for the array length.) That report includes not only the computed sum, but also the "call count" (i.e., the number of times that segSumA() was called during the computation), and the maximum depth to which the recursion ever got.

T(n)categoryHow to Tell
O(logc n)logarithmic T(cn) ≈ T(n)+1
O(n)linear T(cn)/T(n) ≈ c
O(n·logc n)log-linear T(cn)/T(n) ≈ c + c/logc n
O(n2)quadratic T(2n)/T(n) ≈ 4
O(n3)cubic T(2n)/T(n) ≈ 8
O(cn)exponential T(n+1) ≈ c·T(n)
Use the program to compute the sums of several arrays, each time doubling the array's length. For example, you could start with an array of length 20, then one of length 40, then 80, etc. (For the moment, ignore the output referring to segSumB().)

Write down the results and try to discern the asymptotic growth rates of the "call count" and the "max depth of recursion". The table to the right should provide some aid, as it shows, for several categories of asymptotic growth rate, the (approximate) ratios you could expect between T(2n) and T(n), depending upon T's asymptotic growth rate. Discuss your findings with your lab instructor.

Now notice that the class also has two methods called segSumB(), the second of which is stubbed. Its intended purpose is also to compute the sum of the elements in a given array segment, using recursion. However, the code that you supply for it should be based upon these observations: The sum of the elements in the array segment a[low..high) is

  1. zero, if the array segment is empty (i.e., low = high),
  2. a[low], if low+1 = high (i.e., a[low..high) is of length one)
  3. otherwise, obtained by adding the sum of the elements in the "lower" half of a[low..high) with the sum of the elements in the "upper" half. (Take mid to be halfway between low and high. Then the lower and upper halves of a[low..high) are, respectively, a[low..mid) and a[mid..high).)

Supply the missing code from segSumB() (making sure to retain the calls to entering() and leaving()) and then run the program as you did before, with arrays of several lengths, doubling the length each time. Try to figure out the aymptotic growth rates of the "call counter" and "max recursion depth", and notice how they compare to those of segSumA(). Discuss your findings with your lab instructor.