Search⌘ K
AI Features

Useful Formulas

Explore essential formulas used in asymptotic analysis to better understand time complexity. This lesson helps you recognize common patterns like linear, logarithmic, and quadratic time complexities through practical examples, enhancing your ability to evaluate algorithm performance in coding interviews.

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
...