# Useful Formulas

In this lesson, we'll study some mathematical formulas that make calculating time complexity easier!

## We'll cover the following

## Formulas

Here is a list of handy formulas which can be helpful when calculating the time complexity of an algorithm:

$$$$

Summation |
Equation |
---|---|

$\left(\sum_{i=1}^n c \right) = c + c+ c + \cdots + c$ | $cn$ |

$\left(\sum_{i=1}^n i \right) = 1+2+3+\cdots+n$ | $\frac{n(n+1)}{2}$ |

$\left(\sum_{i=1}^n i^2 \right) = 1 + 4 + 9 + \cdots + n^2$ | $\frac{n(n+1)(2n+1)}{6}$ |

$\left(\sum_{i=0}^n r^i\right) = r^0 + r^1 + r^2 + \cdots + r^n$ | $\frac{(r^{n+1}-1)}{r-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)$ |

$log\;a^n$ | $n\;log\;a$ |

$\sum_{i=1}^n log\;i = log\;1 + log\;2 + ... + log\;n$ $= log (1.2...n)$ | $log\;n!$ |

## General tips

- Every time a list or array gets iterated over $c \times 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(log n)$ runtime.
- Whenever you have a singly nested loop, the problem is most likely in quadratic time.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.