Skip to main content
Engineering LibreTexts

3.1: Classifying MyArrayList methods

  • Page ID
    12736
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    For many methods, we can identify the order of growth by examining the code. For example, here’s the implementation of get from MyArrayList:

    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        return array[index];
    }
    

    Everything in get is constant time, so get is constant time. No problem.

    Now that we’ve classified get, we can classify set, which uses it. Here is our implementation of set from the previous exercise:

     public E set(int index, E element) {
        E old = get(index);
        array[index] = element;
        return old;
    } 

    One slightly clever part of this solution is that it does not check the bounds of the array explicitly; it takes advantage of get, which raises an exception if the index is invalid.

    Everything in set, including the invocation of get, is constant time, so set is also constant time.

    Next we’ll look at some linear methods. For example, here’s my implementation of indexOf:

    public int indexOf(Object target) {
        for (int i = 0; i<size; i++) {
            if (equals(target, array[i])) {
                return i;
            }
        }
        return -1;
    } 
    

    Each time through the loop, indexOf invokes equals, so we have to classify equals first. Here it is:

    private boolean equals(Object target, Object element) {
        if (target == null) {
            return element == null;
        } else {
            return target.equals(element);
        }
    }
    

    This method invokes target.equals; the run time of this method might depend on the size of target or element, but it probably doesn’t depend on the size of the array, so we consider it constant time for purposes of analyzing indexOf.

    Getting back to indexOf, everything inside the loop is constant time, so the next question we have to consider is: how many times does the loop execute?

    If we get lucky, we might find the target object right away and return after testing only one element. If we are unlucky, we might have to test all of the elements. On average, we expect to test half of the elements, so this method is considered linear (except in the unlikely case that we know the target element is at the beginning of the array).

    The analysis of remove is similar. Here’s my implementation:

    public E remove(int index) {
        E element = get(index);
        for (int i=index; i<size-1; i++) {
             array[i] = array[i+1];
        }
        size--;
        return element;
    }
    

    It uses get, which is constant time, and then loops through the array, starting from index. If we remove the element at the end of the list, the loop never runs and this method is constant time. If we remove the first element, we loop through all of the remaining elements, which is linear. So, again, this method is considered linear (except in the special case where we know the element is at the end or a constant distance from the end).


    This page titled 3.1: Classifying MyArrayList methods is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Allen B. Downey (Green Tea Press) .

    • Was this article helpful?