- Firstly, study upper-bound(Big-O), lower-bound(Big-Omega) & Intersection Concept( Big-Theta).
- Time Complexity Order : O(x^x) > O(2^x*x!) > O(x!) > O(2^x) > O(x^2) > O(xlogx) > O(x) > O(logx).
- Amortized Analysis : total expense per operation evaluated for sequence of steps.
- Ignore constants & non-dominant terms.
- Binary Search performs better then ternary search (O(log2n) vs O(log3n)).
- Recursive Runtimes : This can be solved with general formula, branches^depth.
Solving way : Perform algorithm stepwise, count number of iterations for each step. Become the "compiler", generalize pattern for complexity evaluation.
Note : loop - O(n), nested loop - O(n^|nested loop|), log vs divide complexity, branch^depth. These are good for easy small generalizations only. Avoid them standalone complexity numericals.
- O(N+M) : If no relation between them is given then no term can be ignored.
- Avoid shallow analysis with crammed complexity for various flows in programming. Iterative calculation approach is best for solution.
- Tree Basics : Complexity calculation, see how much work is done by this recursive function.
int sum(Node n){
if(node == null)
return 0;
return sum(n.left) + n.value + sum(n.right);
}
- Permutations of a String
void perm(String s){
perm(s,"");
}
void perm(String s, String pre){
if(s.length() == 0)
System.out.println(pre);
else{
for(int i=0;i<s.length();i++){
String rem = s.substring(0,i)+s.substring(i+1);
perm(rem, pre+s.charAt(i));
}
}
}
- Count the digits
int digCount(int n){
int count = 0;
while(n>0){
count++;
n/=10;
}
return count;
}
- Each node is touched only once. With total of n nodes present.
- Total Complexity : Total Permutations * Time to print one * Time for iterative loop.
- Nested Loops : Calculate the exact iterations
- Nested Loops : Iterative Analysis Needed
- Loop Comparisons : Multiplicative Iteration Analysis
- Euclids GCD : Swap & Subtract Logic Complexity
- Find Minimum Path : Non-DP approach
- Find Minimum Path : DP approach
- Amortized Analysis : Multiple Case Scenario