The Big O

You may have seen someone write this:

Why didn’t they just write

Well, remember that List is the interface and
ArrayList and LinkedList are implementations. That means it is
OK to point at the implementations through the interface type –
which is where we started this discussion. But if the variable
is the type of one of the implementations you can point only
at an object of that implementation class or it’s subclasses.

It really all boils down to how you are using the accounts collection.
Are you inserting a lot of objects at the end? In the middle? At the beginning?
Do you search on it?

Let’s start with the ArrayList. It is implemented with – surprise – an array.
If the size of the current ArrayList is 100 and you want to insert an object at the
beginning of the list how many guys need to move to the next index? Right, 100. What if the size is 5? Again a no-brainer: 5. So if the size is N, the time it takes to insert at the beginning
depends on the value for N. A size of 2 is twice as long as 1, 3 is three times as long as 1, etc.
so we can say the efficiency for insertion is linear.

ArrayList insertion efficiency = N

But if we swap out a LinkedList for the ArrayList (because we profiled our actual code
execution and found we did a lot of insertion at the beginning) we get different results.
When you insert an object into a LinkedList no data needs to move as with the ArrayList.
A few pointers need to be updated. So, the number of elements in the LinkedList doesn’t
matter for this operation. Saying that another way, the time it takes for insertion is constant.

LinkedList insertion efficiency = 1 (constant)

I'm not trying to sell you a used LinkedList. The tables are turned if we look at the efficiency of
a get operation. One cool things about arrays it that if you want element number 1000 you can access it
directly. It doesn’t matter how big the array is. Right, that is O(1) or constant time.
But a get for a (singly) LinkedList does depend on the size since you start with the beginning of the list and
follow each link until you get the one you want. So, that is linear or O(N).
The implementation of java.util.LinkedList is a doubly linked list which maintains a head and a tail element
so get is a bit more efficient than O(N).

A mathemetician developed a notation that has become know as “big o” for analysis like this.
The O (originally an omicron but now commonly just a capital O not zero) stands for “order”.
The order of LinkedList insertion would be O(1) and for the ArrayList O(N) where N is the number of elements
in the collection.

Some efficiencies

O(1)

constant time, 10 ns

O(log N)

logarithmic time, 200 ns

O(N)

linear time, 10.5ms

O(N log N)

n log n time, 210 ms

O(N ^ 2)

quadratic time, 3.05 hours

O(N ^ 3)

cubic time, 365 years

O(2 ^ N)

exponential, 10 ^ (10 ^ 5) years

When I was a music major I learned about the difference between O(N log N) and O(N ^ 2) the hard way.
On my state of the art NeXT (which was equipped with a DSP chip) I started my algorithms using a
Discreet Fourier Transform. I didn’t pay attention to the fact that the DFT runs in quadratic time. I would
set up a process, go to bed and look/listen to the results in the morning. Not very efficient. On the
other hand the Fast Fourier Transform runs in O(N log N) time. Look at the sample times above to see how
much time I saved.

Other things to consider when choosing the List implementation

ArrayList advantages

• simple to implement
• no overhead for each element
• fast random access

disadvantages

• uses memory proportional to capacity and not number of objects actually contained
• capacity is fixed but is reallocated when needed

Linked List advantages

• uses memory proportional to number of items
• is not limited in capacity

disadvantages

• a bit of overhead for each element (is wrapped in a LinkedList.Entry)
• slow random access