Computational Cost

Mathematical Series

Sums

$\sum_{i = 0}^{n} 1 = θ (n)$
$\sum_{i = 0}^{n} i = θ (n^{2})$

$\sum_{i = 0}^{n} 2^{i} = θ (2^{n})$
$\sum_{i = 0}^{n} c^{i} = \frac{c ^{n + 1} - 1}{c - 1}, c > 1$
$\sum_{i = 0}^{n} c^{i} = θ (1), c < 1$
$\sum_{i = 0}^{n} i c^{i} = θ (n c^{n}), c > 1$

$\sum_{i = 0}^{n} lo g i = θ (n lo g n)$
$\sum_{i = 0}^{n} lo g^{c} i = θ (n lo g^{c} n)$

$\sum_{i = 0}^{n} \frac{1}{i} = θ (lo g n)$
$\sum_{i = 0}^{n} \frac{1}{c ^{i}} = θ (1)$