Formulas
Here is a list of handy formulas, which can be helpful when calculating the time complexity of an algorithm:
Summation |
Equation |
(∑i=1nc)=c+c+c+⋯+c |
cn |
(∑i=1ni)=1+2+3+⋯+n |
2n(n+1) |
(∑i=1ni2)=1+4+9+⋯+n2 |
6n(n+1)(2n+1) |
(∑i=0nri)=r0+r1+r2+⋯+rn |
r−1(rn+1−1) |
∑i=0n2i=20+21+...+2n |
2n+1−1 |
Here are some of the formulas dealing with logarithmic expressions:
Logarithmic Expressions |
Equivalent Expression |
log(a∗b) |
log(a)+log(b) |
log(a/b) |
log(a)−log(b) |
logan |
nloga |
∑i=1nlogi=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 likely be in O(logn) runtime.
- Whenever you have a singly nested loop, the problem is most likely in quadratic time.