Discrete Mathematics for Computing (Draft)

About. In this section, it is necessary to provide definitions of example routines. The routines are not written in any particular language -- in fact, most won’t work in any language as you see them written here. Instead, the routines are provided via some pseudocode -- something about halfway between human preferrable and computer readable. Since we are working with arrays, it is useful to have some convention about how to access individual array elements. Throughout this section, we use myArray[0] to access the element in the left-most slot of the myArray object. We use myArray[i] to access the element in the \(i^{th}\) slot of myArray, remembering that the left-most item occupies the \(0^{th}\) slot of myArray.

Indexing from 0 may seem awkward to those of you who are just beginning your computing careers, but this is the case for many of the most popular computing languages. For this reason, we adopt 0-based indexing here.

Complete the following checkpoint exercises to gain some familiarity with analyzing operations within a function. For reasons that will become clear later in the section, you’ll be asked to ignore any "operations" required to initialize variables, initialize a loop, or return a result back to the computing environment. Additionally, you can consider lines combining arithmetic operations and updating a stored value to be a single operation. That is, x = x + i can be considered a single operation in the checkpoint items below. The reason we can do this will be addressed when big-O notation is introduced later in the section.

Note that in the first three interactive problems above, the size of the input array didn’t matter. That is, number of operations required to arrive at the value to be returned did not depend on the length of the input array. If you didn’t notice that on your own, try regenerating new versions of the embedded examples and working through the examples again. In the final example, however, the number of operations required to complete before arriving at the value to be returned did depend on the length of the input array. Input arrays with more elements require more calculations, and so it should be expected that, as this sum_array_values() routine is applied to larger and larger arrays, it takes longer to run. How much longer run-time should we expect if the length of the input array were to, let’s say, double in length? Should we expect the routine to take approximately twice as long? More time? Less than that? How can we tell? This is the job of big-O notation.

Consider a routine which takes an array as input and then produces some output. The run-time complexity of the algorithm describes the order of the number of operations to be done in transforming the input array into the output, as a function of the length of the input array. Traditionally, the run-time complexity has been written using big-O notation, which looks like \(O\left(f\left(n\right)\right)\text{,}\) where \(f\left(n\right)\) is a function of the length of the input array. We’ll see some examples below.

def return_first(array):
  return array[0]

def sum_first_two(array):
  a = array[0]
  b = array[1]
  total = a + b

  return total

We saw in the previous example that there is no distinction made between \(O\left(1\right)\) and \(O\left(3\right)\text{,}\) or even \(O\left(10^6\right)\text{,}\) for that matter. All of these denote constant run-time, and so their big-O description of complexity is \(O\left(1\right)\text{.}\) We say that such routines have constant run-time, since the time required to run the routine does not change as the size of the input array changes.

Let’s see how the run-time complexity grows for some more interesting routines in the examples below.

def array_product(array):
  myProd = 1
  for element in array:
    myProd = myProd*element

  return myProd

def array_product_difference(array):
  myValue = 1
  for element in array:
    myValue = myValue - element
    myValue = myValue * element
        
  return myValue

NOTE: Need to decide whether setting up a loop or returning values should be counted as an "operation" in determining the run-time complexities -- I’ll reach out to the CS department about the choice they currently make in Analysis of Algorithms.

def detect_product(array):
  for element_a in array:
    for element_b in array:
      for element_c in array:
        if element_a*element_b == element_c:
          return TRUE
        
  return FALSE

Complete the examples below to verify your grasp of algorithmic complexity and big-O notation. Please note that the algorithms are written in pseudocode, and the algorithms don’t necessarily claim to solve their corresponding challenge in the most efficient manner possible. Your answers should describe the algorithmic complexity of the routines as written in the sample problems. Interested readers may try writing working versions of these routines in a language of their choice, and are invited to think about optimizing the algorithms.