Algorithms
Basic rules of complexity definition for removing terms:
- Multiplicative constants can be omitted: 14n2 becomes n2.
- n^a dominates n^b if a > b: for instance, n^2 dominates n.
- Any exponential dominates any polynomial: 3^n dominates n^5 (it even dominates 2^n).
- Likewise, any polynomial dominates any logarithm: n dominates (log n)^3. This also means, for example, that n^2 dominates n* log n.
Techniques to think of counter examples:
- Think small
- Think exhaustively: All possibilities by adding to general cases
Huntfor the weakness: understand the problem statement and try to find loopholes- Go for a tie: Attacking greedy procedures
- Extreme examples:
Searching for solution to problem needs you to know first the type of problem it falls into:
-
Permutations: They are likely the object in question whenever your problem seeks an “arrangement,” “tour,” “ordering,” or “sequence.”
-
Subsets are likely the object in question whenever your problem seeks a “cluster,” “collection,” “committee,” “group,” “packaging,” or “selection.”
-
Trees: Hierarchial relations whenever your problem seeks a “hierarchy,” “dominance relationship,” “ancestor/descendant relationship,” or “taxonomy.”
-
Graphs: relationships between arbitrary pairs of objects Graphs are likely the object in question whenever you seek a “network,” “circuit,” “web,” or “relationship.”
-
Points: whenever your problems work on “sites,” “positions,” “data records,” or “locations.”
-
Polygons: working on “shapes,” “regions,” “configurations,” or “boundaries.”
-
Strings: dealing with “text,” “characters,” ,“patterns,” or “labels.”
Some intuitions behind runtime :
-
n! will be useless after n > 20
-
For upto n=10 all algorithms look similar.
-
2^n is useless after 40
-
n^2 is hopeless after a million
-
linear and nlogn are useful upto a billion
-
logn is useful for any number that comes up.
Types of function classes based on O(n) rule:
-
Constant time
-
Logarithmic time
-
Linear
-
Superlinear
-
Quadratic
-
Cubic
-
Exponential
-
Factorial
Know that changing the base of logarithm has very less impact on time complexity of solution.
Different types of logs: natural, binary, common(base 10) in historical times.
Harmonic numbers sum result in logarithm.
Exponentiation can be done faster using logarithm to convert it to problem of simple multiplication.
Multiplication of matrices requires 3 loops so it’s complexity is n^3.
Advanced type of function classes for complexity analysis:
-
Inverse ackerman’s function alpha(n): Used in analysis of Union Field Data Structures
-
Loglogn
-
logn / loglogn : grows even slower than logn
-
log^2(n): The “log squared” function typically arises in the design of intricate nested data structures, where each node in (say) a binary tree represents another data structure, perhaps ordered on a different key.
-
Sublinear polynomials: root(n) and so on.
-
n^(1+epsilon) : amazing type, highlighted now for reference
Limits and dominance:
f(n) dominates g(n) if lim(n→∞) [g(n)/f(n)] = 0
e.g. 2n^2 is greater than n^2 but doesn’t dominate.
n^3 will though dominate n^2.
For any two polynomials, namely that n^a dominates n^b if a > b
Exponential with higher base dominates. e.g. 3^n over 2^n
A more advanced dominance order:
n! » c^n» n3» n2» n^(1+eps)» n log n» n» √n» log^2(n)» logn» log n/ log log n» log log n» α(n)» 1
Data structures:
Basically two types based on how they are stored in memory: Contiguous: Arrays, matrices, heaps, Hash tables
Pointers: Lists, trees, graphs and adjacent lists
Arrays:
Constant time given the index
Space efficiency
Memory locality: A common programming idiom involves iterating through all the elements of a data structure.
Disadv:
Can’t change size dynamically
Dynamic arrays:
Multiply the memory allocated into 2 times, copy the old one to the lower end of new block and operate.
Main disadv:
Copying the contents of the memory : It will take log2 n doublings until the array gets to have n positions. However, most elements do not suffer much upheaval. Indeed, the (n/2 + 1)st through nth elements will move at most once and might never have to move at all.
Thus, each of the n elements move only two times on average, and the total work of managing the dynamic array is the same O(n) as it would have been if a single array of sufficient size had been allocated in advance!
Questions to answer before sorting:
- Order of sorting
- Sorting just the key or the entire records
- What to do with equal keys? : Leave as the original permutation or resort to some another form of sorting criterion as secondary.
- What about non numerical data?