Data Structures for Coding Interviews in Java/

...

/

Useful Formulae

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+1−1)r−1\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.

Access this course and 1400+ top-rated courses and projects.