User:TheEternalVortex

From Wikipedia, the free encyclopedia

\sum_{n=1}^\infty \frac{n^x}{n!}

X = {{B \times A + B + A(A \cdot B)} \over {A \cdot A + 1}}

a_{n-1}^2 - 2 a_{n-2} = r_1^2 + \cdots + r_n^2 \geq n (r_1^2 \cdots r_n^2)^{1/n} = n (a_0^2)^{1/n} = n

f_n(x) = \int_0^{1-x} f_{n-1}(t) dt , \, \, \, f_0(x) = 1

\sum_{i=1}^n d(\mathbf{x}, \mathbf{x_i}) w_i

For the analysis we will count compares and arithmetic operations. There is no multiplication/division used so they should all be roughly the same time.

Sequential search does 2 compares per iteration and one increment per iteration. When searching for an item in the array we expect n/2 iterations, and n iterations if searching for an item not in the array. Thus the expected number of compares+increments is E(C) = 3(0.1(n) + 0.9(n / 2)) = 0.3n + 1.35n = 1.65n.

Binary search always does lg n iterations (in this implementation). Each iteration it does 2 compares, 1 subtract, 1 add, 1 bitshift, and 1 assignment, for 6 total operations, regardless of whether the item is found or not. So we get 6 lg n. Binary search also does 2 assignments and 2 compares and 1 or no matter what n, so we actually have 5 + 6 lg n.

Empirically about n = 50, numerically ~18.

\mathbf{P}(U + V \leq a) = \int_{-\infty}^\infty \mathbf{P}(U + V \leq a | V = x) dx = \int_{-\infty}^\infty \mathbf{P}(U \leq a - x) dx