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
- All operations are O (n) except for get(index) and addLast(object) (unless resize needed) which are O (1)
- 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.
- O (1) if collisions are handled well.
- 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).