theory

**Definition: ** An algorithm is a finite set of discrete statements (or Steps) in some particular sequence (or Order) to accomplish a predefined particular task. **Properties: ** An algorithm must have the following properties: Input(s) : An algorithm must have one(1) or more pre-specified input(s). Output(s) : An algorithm must have one(1) or more output(s). Definiteness : Each steps of an algorithm must define clearly (i.e. without any confusion or Contradiction or Ambiguity). [Read More]

A hash table is primarily used to keep track of an evolving set of stuff by using a key. It is good for inserting, deleting, and lookups. It is also sometimes referred to as a “dictionary.” They are similar to array in a way, that array gives information at the index very fast, if you know the index. Suppose, your friend names are integer, and you save the number in the array. [Read More]

Definition A balanced search tree is a tree which can provide operations like insert, delete and search in O(lg n) where n is the height of tree and lg n is height. Motivation behind Balanced Search tree Properties of sorted array Consider the sorted array. If we have a sorted array, what kinds of operations can we perform on it? Binary search in O(logn) time. (We use binary search) Select element given ith order statistic in O(1) Computing min/max of array - O(1) Predecessor/Successor - O(1), just find that element and return one before/after it Rank - how many keys stored are less than or equal to the key - O(logn) Output in sorted order - O(n) Simply using a sorted array would be unacceptable for insertion/deletion because it could use O(n) time. [Read More]