Useful Formulae

Formulae

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}$

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, it will most probably be in $O(log n)$ runtime.
3. Whenever you have a single nested loop, the problem is most likely in quadratic time.

---

In the next lesson, we will discuss some common scenarios and how you can calculate their complexities.