Useful Formulae

In this lesson, we'll study some mathematical formulae that would 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
(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}
i=0n2i=20+21+...+2n\sum_{i=0}^n 2^i = 2^0 + 2^1 + ... + 2^n 2n+112^{n+1} - 1

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  anlog\;a^n n  log  an\;log\;a
i=1nlog  i=log  1+log  2+...+log  n\sum_{i=1}^n log\;i = log\;1 + log\;2 + ... + log\;n =log(1.2...n)= log (1.2...n) log  n!log\;n!

General Tips

  1. Every time a list or array gets iterated over c×lengthc \times length times, it is most likely in O(n)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(logn)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 80+ hands-on prep courses.