Content deleted Content added
→See also: add karger's algorithm, another neat example |
→Motivation: "See Big O Notation" => "See Big Theta Notation" because the time complexity notation used was Big Theta, and the surrounding context made it clear that the existing Big Theta notation was used correctly. |
||
Line 32:
:<math> \lim_{n \to \infty} \sum_{i = 1}^{n} \frac{i}{2^i} = 2</math>
Since it is constant the expected run time over many calls is <math>\Theta(1)</math>. (See [[Big
Monte Carlo algorithm:
| |||