해당 페이지에서는 알고리즘의 Time Complexity를 계산할 때 참고할 수 있도록 급수의 Big-O notation을 정리하였다. Recurrence(재귀식)는 알고리즘에서 매우 많이 쓰이는 수학적 개념이다.
$\begin{aligned} f(n) = 1+2+…+n = \sum_{i=1}^n i = \frac {n(n+1)} {2} = O(n^2) \end{aligned}$
$\begin{aligned} f(n) = 1+3+5+…+(2n-1) = \sum_{i=1}^n (2i-1) = n^2 = O(n^2) \end{aligned}$
$\begin{aligned} f(n) = 1^2+2^2+…+n^2 = \sum_{i=1}^n i^2 = \frac {n(n+1)(2n+1)} {6} = O(n^3) \end{aligned}$
$\begin{aligned} f(n) = 1^3+2^3+…+n^3 = \sum_{i=1}^n i^3 = O(n^4) \end{aligned}$
$\begin{aligned} f(n) = 1^4+5^4+9^4+…+(4n-3)^4 = \sum_{i=1}^n (4i-3)^4 = O(n^5) \end{aligned}$
$\begin{aligned} f(n) = 1 + 3 + 3^2 + … + 3^n = \sum_{i=1}^n 3^i = \frac {3^{n+1}-1} {3-1} = O(3^n) \end{aligned}$
$\begin{aligned} f(n) = \frac 1 1 + \frac 1 2 + \frac 1 3 + … + \frac 1 n = \sum_{i=1}^n \frac 1 i \approx 1 + \int_1^n \frac 1 xdx = 1 + \ln(n) - \ln(1) = O(\ln(n)) \end{aligned}$
$\begin{aligned} f(n) = \frac 1 {1^2} + \frac 1 {2^2} + \frac 1 {3^2} + … + \frac 1 {n^2} = \sum_{i=1}^n \frac 1 {i^2} \approx 1 + \int_1^n \frac 1 {x^2} dx = 1 + \frac 1 1 - \frac 1 n = O(1) \end{aligned}$