Useful Formulas

Study some mathematical formulas that make calculating time complexity easier.

We'll cover the following...

Formulas

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

Summation

Equation

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

cncn

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

n(n+1)2\frac{n(n+1)}{2}

(i=1ni2)=1+4+9++n2\left(\sum_{i=1}^n i^2 \right) = 1 + 4 + 9 + \cdots + n^2

n(n+1)(2n+1)6\frac{n(n+1)(2n+1)}{6}

(i=0nri)=r0+r1+r2++rn\left(\sum_{i=0}^n r^i\right) = r^0 + r^1 + r^2 + \cdots + r^n

(rn+11)r1\frac{(r^{n+1}-1)}{r-1}

Here are some of the formulas dealing with logarithmic expressions:

Logrithmtic Expressions

Equivalent Expression

log  (a    b)\log \;(a\;*\;b)

log  (a)+log  (b)\log\;(a) + \log\;(b)

log  (a  /  b)\log \;(a\;/\;b)

log  (a)log  (b)\log\;(a) - \log\;(b)

log  an\log\;a^n

n  log  an\;\log\;a

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

log  n!\log\;n!

General tips

  • Every time a list or array gets iterated over c×lengthc \times length
...