Algorithmic Analysis of Data Structures

Algorithmic analysis

While each data container is implemented differently, due to different tradeoffs between storage space and algorithmic complexity, it is useful to define a set of core tests for algorithmic analysis of data structures.

We begin with lists, which are arguably the simplest.

Big O complexity analysis

To perform a big O complexity analysis, we utilize random but seeded inputs that statistically sample the input space in a representative way. This ensures we aren't getting stuck measuring the runtime of a worst-case or best-case, and thus getting a skewed view of the algorithm.

Different kinds of timing tests, like adding and removing at a high, balanced rate and having a near-empty queue with high throughput.

Testing different operation times versus N, to plot on graphs and verify our code is correct.

Where do we start? Let's start with creating and removing items from a list.

Adda lotsa items, time the amortized cost of expanding..

Memory usage

No way to measure memory usage of objects in-memory, we are left on our own to performing memory profiling.

Linked Lists

Investigation of linked list scaling behavior (isee Linked Lists/Java/Timing) shows O(1) time per add or add/remove operation, both for a long sequence of add operations and a 75/25 mix of add/remove operations. Output from a timing script is shown here:

Timing script link: https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists/Timing.java

Generic templated linked list being tested against the Java Collections API. TLinkedList class link: See https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists/TLinkedList.java