Test 2 Study Guide

Bubble sort and QuickSort both have worst-case complexity of \(O(n^2)\). MergeSort has a worst-case complexity of \(O(n \log n)\).

QuickSort’s expected worst-case complexity is \(O(n \log n)\). Also, QuickSort is an in-place sort, meaning that it performs less copying than MergeSort.

An in-place sorting algorithm is one in which the contents of the array are sorted while remaining within the array.

There is no recursive base case in the provided pseudocode. If this code were executed, it would break the list down into paritions of size 0 and keep trying to split those size 0 partitions indefinitely. We need to add a condition that does not try to sort if the array is of size less than two.

Any partition function which correctly organizes the array into a “low section” and a “high section”, returning the index of the pivot between them, is acceptable. Here’s the Hoare partitioning algorithm which was discussed in Section 1:

partition(array, left, right):
    pivot_val = array[right]
    l = left
    r = right-1
    while l <= r
        if array[l] <= pivot_val:
            l += 1
        elif array[r] >= pivot_val:
            r -= 1
        else:
            swap(array, l, r)
    swap(array, l, right)
    return l

Here’s the Lomuto algorithm which was discussed in Section 2:

Function partition(array, start, end)
  pivot <- array[end]
  frontier <- start
  fence <- start
  While frontier < end
    If array[frontier] < pivot
      swap array[frontier] with array[fence]
      fence <- fence + 1
    EndIf
    frontier <- frontier + 1
  EndWhile
  swap array[end] with array[fence]
  Return fence
EndFunction

Function merge(a1, a2, am)
  i <- 0
  j <- 0
  k <- 0
  While i < length(a1) And j < length(a2)
    If a1[i] < a2[j]
      am[k] <- a1[i]
      i <- i + 1
      k <- k + 1
    Else
      am[k] <- a2[j]
      j <- j + 1
      k <- k + 1
    EndIf
  EndWhile
  While i < length(a1)
    am[k] <- a1[i]
    i <- i + 1
    k <- k + 1
  EndWhile
  While j < length(a2)
    am[k] <- a2[j]
    j <- j + 1
    k <- k + 1
  EndWhile
EndFunction

(This is a “reverse” proof.)

We want to show that \(f(n)\) is \(O(n)\). By definition, this is to claim that \(\exists c>0, k\geq 1.\ \forall n \geq k.\ \frac{n^2+1}{n} \leq cn\).

Let \(k=1\) and \(c=2\). Then it suffices to show that \(\forall n \geq 1.\ \frac{n^2+1}{n} \leq 2n\). We can redistribute the let side to read \(\forall n \geq 1.\ n + \frac{1}{n} \leq 2n\). We have from algebra that, if \(a \leq c\) and \(b \leq d\), then \(a + c \leq b + d\); therefore, it suffices to show both that \(\forall n \geq 1. n \leq n\) and also that \(\forall n \geq 1. \frac{1}{n} \leq n\). The prior is true by definition of equality. For the latter, we multiply both sides by \(n\) (a positive number) to get \(\forall n \geq 1. 1 \leq n^2\); we take the square root of both sides to get \(\forall n \geq 1. 1 \leq n\), which is immediately true. As these two points are sufficient to show the original statement, we conclude that \(f(n)\) is \(O(n)\).

(This is a “forward” proof.)

(This is a limit-based “reverse” proof.)

We aim to prove that \(f(n) = (n+1)(n-1)\) is \(O(n^2)\). By definition, this is to say that \(\lim\limits_{n\to\infty} \dfrac{(n+1)(n-1)}{n^2} = c\) for some constant c. By distribution, this is to say that \(\lim\limits_{n\to\infty} \dfrac{n^2-1}{n^2} = c\).

By the sum law for limits, this is equivalent to the statement \(\left(\lim\limits_{n\to\infty} 1\right) - \left(\lim\limits_{n\to\infty} \dfrac{1}{n^2}\right) = c\). The limit of a constant is the constant itself. The second term in this equation has \(n\) only in the denominator, so this limit is zero. It therefore suffices to show \(1 - 0 = c\) for some constant \(c\), which is true.

An ADT is a description of how data can be accessed and manipulated. In other words, an ADT is an interface allowing the caller to store and retrieve data. A data structure is a concrete realization of an ADT; data structures give specific algorithms to implement the interface that the ADT describes.

Two examples of ADTs are lists and stacks. Lists and stacks are both defined by a collection of routines that allow a user to store and manipulate data (e.g. insertAtHead, peekTail, etc. for list; pop, push, etc. for stack). Two examples of data structures are linked lists and array lists. Both linked lists and array lists are concrete implementations of the list ADT; each of them give implementations for the interface that the list ADT describes.

List and Stack are two different ADTs. The List ADT supports a variety of operations (such as get by index) that a Stack does not. A Stack may be implemented using a List but is not a kind of List.

We might use a Stack instead of a List if the operations provided by Stack are enough for our algorithm. By using a “weaker” data structure, the algorithm that uses it is easier to verify as correct since it’s easier to understand how the data structure behaves.

Amortized complexity is the average complexity of an algorithm over a sequence of calls to it. For instance, the amortized worst-case complexity of ArrayList’s insertAtTail is \(O(1)\) even though the worst case complexity is \(O(n)\): on any given call to insertAtTail, \(O(n)\) is the worst complexity that can occur. However, a sequence of \(n\) calls to insertAtTail on the same list has time complexity \(O(n)\) so, on average once the sequence is finished, each call can be assigned \(O(1)\) time.

Note that this stack diagram does not include a tail pointer, although it wouldn’t be wrong to do so.