Formulas
Here is a list of handy formulas which can be helpful when calculating the time complexity of an algorithm:
Summation |
Equation |
(∑i=1n​c)=c+c+c+⋯+c |
cn |
(∑i=1n​i)=1+2+3+⋯+n |
2n(n+1)​ |
(∑i=1n​i2)=1+4+9+⋯+n2 |
6n(n+1)(2n+1)​ |
(∑i=0n​ri)=r0+r1+r2+⋯+rn |
r−1(rn+1−1)​ |
∑i=0n​2i=20+21+...+2n |
2n+1−1 |
Some of the formulas dealing with logarithmic expressions:
Logrithmtic expressions |
Equivalent Expression |
log(a∗b) |
log(a)+log(b) |
log(a/b) |
log(a)−log(b) |
logan |
nloga |
∑i=1n​logi=log1+log2+...+logn =log(1.2...n) |
logn! |
General Tips
- Every time a list or array gets iterated over c×length times, it is most likely in O(n) time.
- When you see a problem where the number of elements in the problem space gets halved each time, that will most probably be in O(logn) runtime.
- Whenever you have a singly nested loop, the problem is most likely in quadratic time.