This chapter kills two birds with one stone: I present solutions to the previous exercise and demonstrate a way to classify algorithms using **amortized analysis**.

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); ...

Start Free Trial

No credit card required