This note has some summary points from my study of algorithms and algorithmic analysis. If you have little or no idea of the concepts I will talk about, this note may not be so helpful to you. I only post these here to serve as a quick note or as a refresher about these concepts should the need arise. In that case, I suggest you take an advanced course on algorithms and data structures first. Nevertheless, if you are interested in discussing any of the concepts here I will be glad to be of help.

### Data Structures Basics

**ArrayList**

- All operations are
**O (n)**except for**get(index) and****addLast****(object)**(unless resize needed) which are**O (1)**

**LinkedList**

- All operations are
**O (n)**except for**addFirst****(object) and****addLast****(object)**which are**O (1)**

**Stacks and Queues**

- All operations are in
**O (1)**time.

**Hash Tables**

- O (1) if collisions are handled well.
- Rehashing
**Separate chaining**provides a way to handle collisions by placing in a list all key/value pairs for which the hash values associated with the key are equal: All key/value pairs belonging to the same slot are lined up in a list that lives in that slot.- O(α) on average where α = m/n – where n is the number of slots available and m is the number of elements.

**Binary Search Trees**

- Sorts by building a BST with the input, then reading by in-order traversal.
- The average depth of a node in a randomly built BST having n nodes is O(log n). Therefore,
**the operations of insert, delete and search perform in****O(****log n) on average.** - The
**cost of using a BST to sort an array is O(****nlog****n)** - The worst case of reading from BST is
**O(n^2****)** - worst-case running time of Ω(n).