User:TheEternalVortex

From Wikipedia, the free encyclopedia

You have new messages (last change).

\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

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.

Retrieved from "http://en.wikipedia.org../../../t/h/e/User%7ETheEternalVortex_9d01.html"