Useful Formulae

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

We'll cover the following

Formulae

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}

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, it will most probably be in O(logn)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.

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