# Algorithmic Analysis of Data Structures

### From charlesreid1

## Contents

## 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://git.charlesreid1.com/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://git.charlesreid1.com/cs/java/src/master/lists/linked-lists/TLinkedList.java

**Output:**

N, Add Amortized Walltime Per 1k Builtin (us), Add Amortized Walltime Per 1k SLL (us), Add Amortized Walltime Per 1k DLL (us) 1024, 30.273, 16.602, 30.273, 2048, 26.367, 16.602, 26.367, 4096, 31.250, 10.254, 31.250, 8192, 14.771, 13.916, 14.771, 16384, 17.700, 17.639, 17.700, 32768, 15.594, 6.989, 15.594, 65536, 15.274, 7.874, 15.274, 131072, 14.778, 8.125, 14.778, 262144, 15.751, 8.671, 15.751, N, Add Remove Amortized Walltime Per 1k Builtin (us), Add Remove Amortized Walltime Per 1k SLL (us), Add Remove Amortized Walltime Per 1k DLL (us) 1000, 43.000, 29.000 27.000 4000, 29.000, 19.250 18.500 16000, 21.313, 18.500 18.813 64000, 21.672, 18.969 18.859 256000, 21.738, 18.906 19.586

The first column shows the size of the input, the number of elements being added or removed from the list. (N is an operations count.) This time, normalized per 1000 operations, is shown for three cases:

- Second column - time in microseconds per 1000 operations for Java Collections LinkedList
- Third column - time in microseconds per 1000 operations for TLinkedList, singly-linked generic linked list
- Fourth column - time in microseconds per 1000 operations for DLinkedList, doubly-linked generic linked list

You can see that the amortized runtime, as the input size scales from thousands to millions, remains constant for all three types, except at small sizes where algorithm performance is harder to compare.

## Flags

Data StructuresThis is the staging ground for computer science notes as part of the 2017 CS Study Plan.
Classes of data structures: Abstract Data Types Array-based and Link-based memory management: ArrayLists and Linked Lists Algorithmic Analysis of Data Structures: Algorithmic Analysis of Data Structures Advanced data structures: Advanced Data Structures
· Template:DataStructuresFlag · e |

ArraysSeries on Data Structures Python: Arrays/Python Java: Arrays/Java Categories: Category:Python Arrays
· Template:ArraysFlagBase · e |

Stacks and QueuesSeries on Data Structures
StacksQueues/Python StacksQueues/Python/LinkedStack
StacksQueues/Java StacksQueues/Java/LinkedStack
Postfix_Expressions#Stacks
· Template:StacksQueuesFlagBase · e |

Priority Queues and HeapsSeries on Data Structures
Priority Queues/Heap
· Template:PriorityQueuesFlagBase · e |

Linked ListSeries on Data Structures
· Template:LinkedListFlagBase · e |

TreesSeries on Data Structures Abstract data type: Trees/ADT Concrete implementations: Trees/LinkedTree
Preorder traversal: Trees/Preorder Postorder traversal: Trees/Postorder In-Order traversal: Binary Trees/Inorder Breadth-First Search: BFS Breadth-First Traversal: BFT Depth-First Search: DFS Depth-First Traversal: DFT OOP Principles for Traversal: Tree Traversal/OOP Tree operations: Trees/Operations Performance
Finding Minimum in Log N Time: Tree/LogN Min Search
Abstract data type: Binary Trees/ADT Concrete implementations: Binary Trees/LinkedBinTree Binary Trees/Cheat Sheet
· Template:TreesFlagBase · e |

Search TreesSeries on Data Structures
Binary Search Trees Trees/OOP
(Note that heaps are also value-sorting trees with minimums at the top. See Template:PriorityQueuesFlag and Priority Queues.)
· Template:SearchTreesFlagBase · e |

Maps and DictionariesSeries on Data Structures
Maps Map implementations: Maps/AbstractMap Dictionary implementations: Dictionaries/LinkedDict
Hash Maps/OOP Hash Maps/Dynamic Resizing Hash functions: Hash Functions Hash map implementations: Hash Maps/AbstractHashMap
Skip Lists Java implementations: SkipList
Sets
· Template:MapsFlagBase · e |