# Useful Formulas

In this lesson, we'll study some mathematical formulae 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}$
$\sum_{i=0}^n 2^i = 2^0 + 2^1 + ... + 2^n$ $2^{n+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)$
$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

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

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