search

Tag - Analysis of Algorithms

Two
Sums of geometric series Sun, Jul 23, 2017 02:00 CEST

Among the identities that are useful in the analysis of algorithms, this one shows how sums of geometric series converge when the ratio is smaller than one (in absolute value). It occurs in divide an conquer schemes. For example, it allows to show that hierarchical cuttings for \(n\) hyperplanes in \(d\) dimensions only need space proportional to \(n^d\).

\[ \sum_{i=0}^{\infty} \binom{i+j}{j} x^i = \frac{1}{ {(1-x)}^{j+1} }, \forall j \in \mathbb{N}, \forall x \in (-1,1). \]

Log Log Log Thu, Apr 14, 2016 02:00 CEST

Theorem

$$ \frac{\log n}{\log \log n}! = \Theta(n) $$