Useful Formulae

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

We'll cover the following


Here is a list of handy formulas which can be helpful when calculating the Time Complexity of an algorithm:

(i=1nc)=c+c+c++c\left(\sum_{i=1}^n c \right) = c + c+ c + \cdots + c
(i=1ni)=1+2+3++n\left(\sum_{i=1}^n i \right) = 1+2+3+\cdots+n
(i=1ni2)=1+4+9++n2\left(\sum_{i=1}^n i^2 \right) = 1 + 4 + 9 + \cdots + n^2
(i=0nri)=r0+r1+r2++rn\left(\sum_{i=0}^n r^i\right) = r^0 + r^1 + r^2 + \cdots + r^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, it is most likely in O(logn)O(log n) runtime.

  3. Whenever you have a single nested loop, the problem is most likely in quadratic time.

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