text:
Big O notation

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by German mathematicians Paul Bachmann, Edmund Landau, and others, collectively called Bachmann–Landau notation or asymptotic notation. The letter O was chosen by Bachmann to stand for Ordnung, meaning the order of approximation.

In computer science, big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows. In analytic number theory, big O notation is often used to express a bound on the difference between an arithmetical function and a better understood approximation; a famous example of such a difference is the remainder term in the prime number theorem. Big O notation is also used in many other fields to provide similar estimates.

Big O notation characterizes functions according to their growth rates: different functions with the same asymptotic growth rate may be represented using the same O notation. The letter O is used because the growth rate of a function is also referred to as the order of the function. A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function.

Associated with big O notation are several related notations, using the symbols $o, Ω, ω$, and $Θ$, to describe other kinds of bounds on asymptotic growth rates.

Formal definition
Let $$f$$, the function to be estimated, be a real or complex valued function, and let $$g$$, the comparison function, be a real valued function. Let both functions be defined on some unbounded subset of the positive real numbers, and $$g(x)$$ be strictly positive for all large enough values of $$x$$. One writes $$ f(x) = O\bigl( g(x)\bigr)\quad\text{ as }x\to\infty $$ and it is read "$$f(x)$$ is big O of $$g(x)$$" if the absolute value of $$f(x)$$ is at most a positive constant multiple of $$g(x)$$ for all sufficiently large values of $$x$$. That is, $$f(x) =O\bigl(g(x)\bigr)$$ if there exists a positive real number $$M$$ and a real number $$x_0$$ such that $$|f(x)| \le M g(x) \quad \text{ for all } x \ge x_0.$$ In many contexts, the assumption that we are interested in the growth rate as the variable $$x$$ goes to infinity is left unstated, and one writes more simply that $$f(x) = O\bigl( g(x) \bigr).$$ The notation can also be used to describe the behavior of $$f$$ near some real number $$a$$ (often, $$a=0$$): we say $$f(x) = O\bigl( g(x) \bigr)\quad\text{ as }x \to a$$ if there exist positive numbers $$\delta$$ and $$M$$ such that for all defined $$x$$ with $0 < $$|f(x)| \le M g(x).$$ As $$g(x)$$ is chosen to be strictly positive for such values of $$x$$, both of these definitions can be unified using the limit superior: $$f(x) = O\bigl( g(x) \bigr) \quad \text{ as } x \to a$$ if $$\limsup_{x\to a} \frac{\left|f(x)\right|}{g(x)} < \infty.$$ And in both of these definitions the limit point $$a$$ (whether $$\infty$$ or not) is a cluster point of the domains of $$f$$ and $$g$$, i. e., in every neighbourhood of $$a$$ there have to be infinitely many points in common. Moreover, as pointed out in the article about the limit inferior and limit superior, the $$\textstyle \limsup_{x\to a}$$ (at least on the extended real number line) always exists.

In computer science, a slightly more restrictive definition is common: $$f$$ and $$g$$ are both required to be functions from some unbounded subset of the positive integers to the nonnegative real numbers; then $$f(x) = O\bigl(g(x)\bigr)$$ if there exist positive integer numbers $$M$$ and $$n_0$$ such that $$f(n) \le M g(n)$$ for all $$ n \ge n_0$$.

Example
In typical usage the $O$ notation is asymptotical, that is, it refers to very large $x$. In this setting, the contribution of the terms that grow "most quickly" will eventually make the other ones irrelevant. As a result, the following simplification rules can be applied: For example, let $f(x)$, and suppose we wish to simplify this function, using $f(x)$ notation, to describe its growth rate as $x$ approaches infinity. This function is the sum of three terms: $f(x) = 6x^{4} − 2x^{3} + 5$, $O$, and $6x^{4}$. Of these three terms, the one with the highest growth rate is the one with the largest exponent as a function of $x$, namely $−2x^{3}$. Now one may apply the second rule: $5$ is a product of $6x^{4}$ and $6x^{4}$ in which the first factor does not depend on $6$. Omitting this factor results in the simplified form $x^{4}$. Thus, we say that $x$ is a "big O" of $x^{4}$. Mathematically, we can write $f(x)$. One may confirm this calculation using the formal definition: let $x^{4}$ and $f(x) = O(x^{4})$. Applying the formal definition from above, the statement that $f(x) = 6x^{4} − 2x^{3} + 5$ is equivalent to its expansion, $$|f(x)| \le M x^4$$ for some suitable choice of a real number $g(x) = x^{4}$ and a positive real number $x$ and for all $f(x) = O(x^{4})$. To prove this, let $x_{0}$ and $x > x_{0}$. Then, for all $x_{0} = 1$: $$\begin{align} &\le 6x^4 + 2x^4 + 5x^4\\ &= 13x^4 \end{align}$$ so $$ |6x^4 - 2x^3 + 5| \le 13 x^4 .$$
 * If $M = 13$ is a sum of several terms, if there is one with largest growth rate, it can be kept, and all others omitted.
 * If $x > x_{0}$ is a product of several factors, any constants (factors in the product that do not depend on $M$) can be omitted.
 * 6x^4 - 2x^3 + 5| &\le 6x^4 + |2x^3| + 5\\

Usage
Big O notation has two main areas of application:
 * In mathematics, it is commonly used to describe how closely a finite series approximates a given function, especially in the case of a truncated Taylor series or asymptotic expansion
 * In computer science, it is useful in the analysis of algorithms

In both applications, the function $g(x)$ appearing within the $O(·)$ is typically chosen to be as simple as possible, omitting constant factors and lower order terms.

There are two formally close, but noticeably different, usages of this notation:
 * infinite asymptotics
 * infinitesimal asymptotics.

This distinction is only in application and not in principle, however—the formal definition for the "big O" is the same for both cases, only with different limits for the function argument.

Infinite asymptotics
Big O notation is useful when analyzing algorithms for efficiency. For example, the time (or the number of steps) it takes to complete a problem of size $N$ might be found to be $T(n) = 4n^{2} − 2n + 2$. As $n$ grows large, the $n^{2}$ term will come to dominate, so that all other terms can be neglected—for instance when $n = 500$, the term $4n^{2}$ is 1000 times as large as the $2n$ term. Ignoring the latter would have negligible effect on the expression's value for most purposes. Further, the coefficients become irrelevant if we compare to any other order of expression, such as an expression containing a term $n^{3}$ or $n^{4}$. Even if $T(n) = 1,000,000n^{2}$, if $U(n) = n^{3}$, the latter will always exceed the former once $n$ grows larger than $1,000,000$, viz. $T(1,000,000) = 1,000,000^{3} = U(1,000,000)$. Additionally, the number of steps depends on the details of the machine model on which the algorithm runs, but different types of machines typically vary by only a constant factor in the number of steps needed to execute an algorithm. So the big O notation captures what remains: we write either
 * $$T(n)= O(n^2) $$

or
 * $$T(n) \in O(n^2) $$

and say that the algorithm has order of $n^{2}$ time complexity. The sign "$=$" is not meant to express "is equal to" in its normal mathematical sense, but rather a more colloquial "is", so the second expression is sometimes considered more accurate (see the "Equals sign" discussion below) while the first is considered by some as an abuse of notation.

Infinitesimal asymptotics
Big O can also be used to describe the error term in an approximation to a mathematical function. The most significant terms are written explicitly, and then the least-significant terms are summarized in a single big O term. Consider, for example, the exponential series and two expressions of it that are valid when $n$ is small:
 * $$\begin{align}

e^x &=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\dotsb &\text{for all } x\\[4pt] &=1+x+\frac{x^2}{2}+O(x^3)                               &\text{as } x\to 0\\[4pt] &=1+x+O(x^2)                                             &\text{as } x\to 0 \end{align}$$ The middle expression (the one with O(x3)) means the absolute-value of the error ex − (1 + x + x2/2) is at most some constant times |x3| when x is close enough to 0.

Properties
If the function $f$ can be written as a finite sum of other functions, then the fastest growing one determines the order of $f(n)$. For example,
 * $$f(n) = 9 \log n + 5 (\log n)^4 + 3n^2 + 2n^3 = O(n^3) \qquad\text{as } n\to\infty .$$

In particular, if a function may be bounded by a polynomial in $n$, then as $x$ tends to infinity, one may disregard lower-order terms of the polynomial. The sets $O(n^{c})$ and $O(c^{n})$ are very different. If $n$ is greater than one, then the latter grows much faster. A function that grows faster than $n^{c}$ for any $n$ is called superpolynomial. One that grows more slowly than any exponential function of the form $c^{n}$ is called subexponential. An algorithm can require time that is both superpolynomial and subexponential; examples of this include the fastest known algorithms for integer factorization and the function $n^{log n}$.

We may ignore any powers of $c$ inside of the logarithms. The set $O(log n)$ is exactly the same as $O(log(n^{c}))$. The logarithms differ only by a constant factor (since $log(n^{c}) = c log n$) and thus the big O notation ignores that. Similarly, logs with different constant bases are equivalent. On the other hand, exponentials with different bases are not of the same order. For example, $2^{n}$ and $3^{n}$ are not of the same order.

Changing units may or may not affect the order of the resulting algorithm. Changing units is equivalent to multiplying the appropriate variable by a constant wherever it appears. For example, if an algorithm runs in the order of $n^{2}$, replacing $c$ by $cn$ means the algorithm runs in the order of $c^{2}n^{2}$, and the big O notation ignores the constant $c^{2}$. This can be written as $c^{2}n^{2} = O(n^{2})$. If, however, an algorithm runs in the order of $2^{n}$, replacing $n$ with $cn$ gives $2^{cn} = (2^{c})^{n}$. This is not equivalent to $2^{n}$ in general. Changing variables may also affect the order of the resulting algorithm. For example, if an algorithm's run time is $O(n)$ when measured in terms of the number $n$ of digits of an input number $n$, then its run time is $O(log x)$ when measured as a function of the input number $n$ itself, because $n = O(log x)$.

Product

 * $$ f_1 = O(g_1) \text{ and } f_2 = O(g_2) \Rightarrow f_1 f_2 = O(g_1  g_2)$$
 * $$f\cdot O(g) = O(f g)$$

Sum
If $$ f_1 = O(g_1)$$ and $$ f_2= O(g_2) $$ then $$ f_1 + f_2 = O(\max(g_1, g_2))$$. It follows that if $$ f_1 = O(g) $$ and $$ f_2 = O(g)$$ then $$ f_1+f_2 \in O(g) $$. In other words, this second statement says that $$O(g)$$ is a convex cone.

Multiplication by a constant
Let $x$ be a nonzero constant. Then $$O(|k| \cdot g) = O(g)$$. In other words, if $$f = O(g)$$, then $$k \cdot f = O(g). $$

Multiple variables
Big O (and little o, Ω, etc.) can also be used with multiple variables. To define big O formally for multiple variables, suppose $$f$$ and $$g$$ are two functions defined on some subset of $$\R^n$$. We say
 * $$f(\mathbf{x})\text{ is }O(g(\mathbf{x}))\quad\text{ as }\mathbf{x}\to\infty$$

if and only if there exist constants $$M$$ and $$C > 0$$ such that $$|f(\mathbf{x})| \le C |g(\mathbf{x})|$$ for all $$\mathbf{x}$$ with $$ x_i \geq M$$ for some $$i.$$ Equivalently, the condition that $$x_i \geq M$$ for some $$i$$ can be written $$\|\mathbf{x}\|_{\infty} \ge M$$, where $$\|\mathbf{x}\|_{\infty}$$ denotes the Chebyshev norm. For example, the statement
 * $$f(n,m) = n^2 + m^3 + O(n+m) \quad\text{ as } n,m\to\infty$$

asserts that there exist constants C and M such that
 * $$ |f(n,m) - (n^2 + m^3)| \le C |n+m|$$

whenever either $$ m \geq M$$ or $$n \geq M$$ holds. This definition allows all of the coordinates of $$\mathbf{x}$$ to increase to infinity. In particular, the statement
 * $$f(n,m) = O(n^m) \quad \text{ as } n,m\to\infty$$

(i.e., $$\exists C \,\exists M \,\forall n \,\forall m\,\cdots$$) is quite different from
 * $$\forall m\colon~f(n,m) = O(n^m) \quad\text{ as } n\to\infty$$

(i.e., $$\forall m \, \exists C \, \exists M \, \forall n \, \cdots$$).

Under this definition, the subset on which a function is defined is significant when generalizing statements from the univariate setting to the multivariate setting. For example, if $$f(n,m)=1$$ and $$g(n,m)=n$$, then $$f(n,m) = O(g(n,m))$$ if we restrict $$f$$ and $$g$$ to $$[1,\infty)^2$$, but not if they are defined on $$[0,\infty)^2$$.

This is not the only generalization of big O to multivariate functions, and in practice, there is some inconsistency in the choice of definition.

Equals sign
The statement "f(x) is O(g(x))" as defined above is usually written as $f(x) = O(g(x))$. Some consider this to be an abuse of notation, since the use of the equals sign could be misleading as it suggests a symmetry that this statement does not have. As de Bruijn says, $O(x) = O(x^{2})$ is true but $O(x^{2}) = O(x)$ is not. Knuth describes such statements as "one-way equalities", since if the sides could be reversed, "we could deduce ridiculous things like $n = n^{2}$ from the identities $n = O(n^{2})$ and $n^{2} = O(n^{2})$." In another letter, Knuth also pointed out that "the equality sign is not symmetric with respect to such notations", as, in this notation, "mathematicians customarily use the = sign as they use the word "is" in English: Aristotle is a man, but a man isn't necessarily Aristotle".

For these reasons, it would be more precise to use set notation and write $f(x) ∈ O(g(x))$ (read as: "f(x) is an element of O(g(x))", or "f(x) is in the set O(g(x))"), thinking of O(g(x)) as the class of all functions h(x) such that $|h(x)| ≤ Cg(x)$ for some positive real number C. However, the use of the equals sign is customary.

Other arithmetic operators
Big O notation can also be used in conjunction with other arithmetic operators in more complicated equations. For example, h(x) + O(f(x)) denotes the collection of functions having the growth of h(x) plus a part whose growth is limited to that of f(x). Thus,
 * $$g(x) = h(x) + O(f(x))$$

expresses the same as
 * $$g(x) - h(x) = O(f(x)).$$

Example
Suppose an algorithm is being developed to operate on a set of n elements. Its developers are interested in finding a function T(n) that will express how long the algorithm will take to run (in some arbitrary measurement of time) in terms of the number of elements in the input set. The algorithm works by first calling a subroutine to sort the elements in the set and then perform its own operations. The sort has a known time complexity of O(n2), and after the subroutine runs the algorithm must take an additional 55n3 + 2n + 10 steps before it terminates. Thus the overall time complexity of the algorithm can be expressed as T(n) = 55n3 + O(n2). Here the terms 2n + 10 are subsumed within the faster-growing O(n2). Again, this usage disregards some of the formal meaning of the "=" symbol, but it does allow one to use the big O notation as a kind of convenient placeholder.

Multiple uses
In more complicated usage, O(·) can appear in different places in an equation, even several times on each side. For example, the following are true for $$n\to\infty$$: $$ \begin{align} (n+1)^2 & = n^2 + O(n), \\ (n + O(n^{1/2})) \cdot (n + O(\log n))^2 & = n^3 + O(n^{5/2}), \\ n^{O(1)} & = O(e^n). \end{align}$$ The meaning of such statements is as follows: for any functions which satisfy each O(·) on the left side, there are some functions satisfying each O(·) on the right side, such that substituting all these functions into the equation makes the two sides equal. For example, the third equation above means: "For any function f(n) = O(1), there is some function g(n) = O(en) such that nf(n) = g(n)." In terms of the "set notation" above, the meaning is that the class of functions represented by the left side is a subset of the class of functions represented by the right side. In this use the "=" is a formal symbol that unlike the usual use of "=" is not a symmetric relation. Thus for example nO(1) = O(en) does not imply the false statement O(en) = nO(1).

Typesetting
Big O is typeset as an italicized uppercase "O", as in the following example: $$O(n^2)$$. In TeX, it is produced by simply typing O inside math mode. Unlike Greek-named Bachmann–Landau notations, it needs no special symbol. Yet, some authors use the calligraphic variant $$\mathcal{O}$$ instead.

Orders of common functions
Here is a list of classes of functions that are commonly encountered when analyzing the running time of an algorithm. In each case, c is a positive constant and n increases without bound. The slower-growing functions are generally listed first.

The statement $$f(n) = O(n!)$$ is sometimes weakened to $$f(n) = O\left(n^n\right)$$ to derive simpler formulas for asymptotic complexity. For any $$k>0$$ and $c > 0$, $$O(n^c(\log n)^k)$$ is a subset of $$O(n^{c+\varepsilon})$$ for any $ \varepsilon > 0$, so may be considered as a polynomial with some bigger order.

Related asymptotic notations
Big O is widely used in computer science. Together with some other related notations, it forms the family of Bachmann–Landau notations.

Little-o notation
Intuitively, the assertion "$f(x)$ is $o(g(x))$" (read "$f(x)$ is little-o of $g(x)$") means that $g(x)$ grows much faster than $f(x)$. As before, let f be a real or complex valued function and g a real valued function, both defined on some unbounded subset of the positive real numbers, such that g(x) is strictly positive for all large enough values of x. One writes
 * $$f(x) = o(g(x)) \quad \text{ as } x \to \infty$$

if for every positive constant $x$ there exists a constant $$x_0$$ such that
 * $$|f(x)| \leq \varepsilon g(x) \quad \text{ for all } x \geq x_0.$$

For example, one has
 * $$2x = o(x^2)$$ and $$1/x = o(1),$$    both as $$ x \to \infty .$$

The difference between the definition of the big-O notation and the definition of little-o is that while the former has to be true for at least one constant M, the latter must hold for every positive constant $ε$, however small. In this way, little-o notation makes a stronger statement than the corresponding big-O notation: every function that is little-o of g is also big-O of g, but not every function that is big-O of g is also little-o of g. For example, $$2x^2 = O(x^2) $$ but $2x^2 \neq o(x^2)$.

As g(x) is nonzero, or at least becomes nonzero beyond a certain point, the relation $$f(x) = o(g(x))$$ is equivalent to
 * $$\lim_{x \to \infty}\frac{f(x)}{g(x)} = 0$$ (and this is in fact how Landau originally defined the little-o notation).

Little-o respects a number of arithmetic operations. For example,
 * if $k$ is a nonzero constant and $$f = o(g)$$ then $$c \cdot f = o(g)$$, and
 * if $$f = o(F)$$ and $$g = o(G)$$ then $$ f \cdot g = o(F \cdot G).$$

It also satisfies a transitivity relation:
 * if $$f = o(g)$$ and $$ g = o(h)$$ then $$f = o(h).$$

Big Omega notation
Another asymptotic notation is $$\Omega$$, read "big omega". There are two widespread and incompatible definitions of the statement

 * $$f(x)=\Omega(g(x))$$ as $$x \to a$$,

where a is some real number, $$\infty$$, or $$-\infty$$, where f and g are real functions defined in a neighbourhood of a, and where g is positive in this neighbourhood.

The Hardy–Littlewood definition is used mainly in analytic number theory, and the Knuth definition mainly in computational complexity theory; the definitions are not equivalent.

The Hardy–Littlewood definition
In 1914 Godfrey Harold Hardy and John Edensor Littlewood introduced the new symbol $$\Omega$$, which is defined as follows:

 * $$f(x) = \Omega(g(x))$$ as $$x\to\infty$$ if $$\limsup_{x \to \infty} \left|\frac{f(x)}{g(x)}\right| > 0.$$

Thus $$f(x)=\Omega(g(x))$$ is the negation of $$f(x)=o(g(x))$$.

In 1916 the same authors introduced the two new symbols $$\Omega_R$$ and $$\Omega_L$$, defined as:

 * $$f(x)=\Omega_R(g(x))$$ as $$x\to\infty$$ if $$\limsup_{x \to \infty} \frac{f(x)}{g(x)}> 0$$;

 * $$f(x)=\Omega_L(g(x))$$ as $$x\to\infty$$ if $$\liminf_{x \to \infty} \frac{f(x)}{g(x)}< 0. $$

These symbols were used by Edmund Landau, with the same meanings, in 1924. After Landau, the notations were never used again exactly thus; $$\Omega_R$$ became $$\Omega_+$$ and $$\Omega_L$$ became $$\Omega_-$$.

These three symbols $$\Omega, \Omega_+, \Omega_-$$, as well as $$f(x)=\Omega_\pm(g(x))$$ (meaning that $$f(x)=\Omega_+(g(x))$$ and $$f(x)=\Omega_-(g(x))$$ are both satisfied), are now currently used in analytic number theory.

Simple examples
We have

 * $$\sin x=\Omega(1)$$ as $$x\to\infty,$$

and more precisely

 * $$\sin x=\Omega_\pm(1)$$ as $$x\to\infty.$$

We have

 * $$\sin x+1=\Omega(1)$$ as $$x\to\infty,$$

and more precisely

 * $$\sin x+1=\Omega_+(1)$$ as $$x\to\infty;$$

however

 * $$\sin x+1\not=\Omega_-(1)$$ as $$x\to\infty.$$

The Knuth definition
In 1976 Donald Knuth published a paper to justify his use of the $$\Omega$$-symbol to describe a stronger property. Knuth wrote: "For all the applications I have seen so far in computer science, a stronger requirement ... is much more appropriate". He defined

 * $$f(x)=\Omega(g(x))\Leftrightarrow g(x)=O(f(x))$$

with the comment: "Although I have changed Hardy and Littlewood's definition of $$\Omega$$, I feel justified in doing so because their definition is by no means in wide use, and because there are other ways to say what they want to say in the comparatively rare cases when their definition applies."

Family of Bachmann–Landau notations
The limit definitions assume $$g(n) > 0$$ for sufficiently large $$n$$. The table is (partly) sorted from smallest to largest, in the sense that $$o,O,\Theta,\sim,  $$ (Knuth's version of) $$\Omega, \omega   $$ on functions correspond to $$<,\leq,\approx,=,   $$$$\geq,>   $$ on the real line (the Hardy–Littlewood version of $$\Omega   $$, however, doesn't correspond to any such description).

Computer science uses the big $$O  $$, big Theta $$\Theta   $$, little $$o   $$, little omega $$\omega   $$ and Knuth's big Omega $$\Omega   $$ notations. Analytic number theory often uses the big $$O  $$, small $$o   $$, Hardy's $$\asymp$$, Hardy–Littlewood's big Omega $$\Omega   $$ (with or without the +, − or ± subscripts) and $$\sim$$ notations. The small omega $$\omega  $$ notation is not used as often in analysis.

Use in computer science
Informally, especially in computer science, the big O notation often can be used somewhat differently to describe an asymptotic tight bound where using big Theta Θ notation might be more factually appropriate in a given context. For example, when considering a function T(n) = 73n3 + 22n2 + 58, all of the following are generally acceptable, but tighter bounds (such as numbers 2 and 3 below) are usually strongly preferred over looser bounds (such as number 1 below). The equivalent English statements are respectively: So while all three statements are true, progressively more information is contained in each. In some fields, however, the big O notation (number 2 in the lists above) would be used more commonly than the big Theta notation (items numbered 3 in the lists above). For example, if T(n) represents the running time of a newly developed algorithm for input size n, the inventors and users of the algorithm might be more inclined to put an upper asymptotic bound on how long it will take to run without making an explicit statement about the lower asymptotic bound.
 * 1) T(n) = O(n100)
 * 2) T(n) = O(n3)
 * 3) T(n) = Θ(n3)
 * 1) T(n) grows asymptotically no faster than n100
 * 2) T(n) grows asymptotically no faster than n3
 * 3) T(n) grows asymptotically as fast as n3.

Other notation
In their book Introduction to Algorithms, Cormen, Leiserson, Rivest and Stein consider the set of functions f which satisfy

 * $$ f(n) = O(g(n))\quad(n\to\infty)~.$$

In a correct notation this set can, for instance, be called O(g), where

$$O(g) = \{ f : \text{there exist positive constants}~c~\text{and}~n_0~\text{such that}~0 \le f(n) \le c g(n) \text{ for all } n \ge n_0 \}.$$

The authors state that the use of equality operator (=) to denote set membership rather than the set membership operator (∈) is an abuse of notation, but that doing so has advantages. Inside an equation or inequality, the use of asymptotic notation stands for an anonymous function in the set O(g), which eliminates lower-order terms, and helps to reduce inessential clutter in equations, for example:

 * $$ 2n^2 + 3n + 1=2n^2 + O(n).$$

Extensions to the Bachmann–Landau notations
Another notation sometimes used in computer science is Õ (read soft-O), which hides polylogarithmic factors. There are two definitions in use: some authors use f(n) = Õ(g(n)) as shorthand for f(n) = O(g(n) logk n) for some k, while others use it as shorthand for f(n) = O(g(n) logk g(n)). When g(n) is polynomial in n, there is no difference; however, the latter definition allows one to say, e.g. that $$n2^n = \tilde O(2^n)$$ while the former definition allows for $$\log^k n = \tilde O(1)$$ for any constant k. Some authors write O* for the same purpose as the latter definition. Essentially, it is big O notation, ignoring logarithmic factors because the growth-rate effects of some other super-logarithmic function indicate a growth-rate explosion for large-sized input parameters that is more important to predicting bad run-time performance than the finer-point effects contributed by the logarithmic-growth factor(s). This notation is often used to obviate the "nitpicking" within growth-rates that are stated as too tightly bounded for the matters at hand (since logk n is always o(nε) for any constant k and any ε > 0).

Also, the L notation, defined as
 * $$L_n[\alpha,c] = e^{(c + o(1))(\ln n)^\alpha(\ln\ln n)^{1-\alpha}},$$

is convenient for functions that are between polynomial and exponential in terms of $\ln n$.

Generalizations and related usages
The generalization to functions taking values in any normed vector space is straightforward (replacing absolute values by norms), where f and g need not take their values in the same space. A generalization to functions g taking values in any topological group is also possible. The "limiting process" $x → x_{o}$ can also be generalized by introducing an arbitrary filter base, i.e. to directed nets f and g. The o notation can be used to define derivatives and differentiability in quite general spaces, and also (asymptotical) equivalence of functions,
 * $$ f\sim g \iff (f-g) \in o(g) $$

which is an equivalence relation and a more restrictive notion than the relationship "f is Θ(g)" from above. (It reduces to lim f / g = 1 if f and g are positive real valued functions.) For example, 2x is Θ(x), but $2x − x$ is not o(x).

History (Bachmann–Landau, Hardy, and Vinogradov notations)
The symbol O was first introduced by number theorist Paul Bachmann in 1894, in the second volume of his book Analytische Zahlentheorie ("analytic number theory"). The number theorist Edmund Landau adopted it, and was thus inspired to introduce in 1909 the notation o; hence both are now called Landau symbols. These notations were used in applied mathematics during the 1950s for asymptotic analysis. The symbol $$\Omega$$ (in the sense "is not an o of") was introduced in 1914 by Hardy and Littlewood. Hardy and Littlewood also introduced in 1916 the symbols $$\Omega_R$$ ("right") and $$\Omega_L$$ ("left"), precursors of the modern symbols $$\Omega_+$$ ("is not smaller than a small o of") and $$\Omega_-$$ ("is not larger than a small o of"). Thus the Omega symbols (with their original meanings) are sometimes also referred to as "Landau symbols". This notation $$\Omega$$ became commonly used in number theory at least since the 1950s.

The symbol $$\sim$$, although it had been used before with different meanings, was given its modern definition by Landau in 1909 and by Hardy in 1910. Just above on the same page of his tract Hardy defined the symbol $$\asymp$$, where $$f(x)\asymp g(x)$$ means that both $$f(x)=O(g(x))$$ and $$g(x)=O(f(x))$$ are satisfied. The notation is still currently used in analytic number theory. In his tract Hardy also proposed the symbol $$\, \asymp\!\!\!\!\!\! -$$, where $$f \asymp\!\!\!\!\!\! - g$$ means that $$ f\sim Kg $$ for some constant $$K\not=0$$.

In the 1970s the big O was popularized in computer science by Donald Knuth, who proposed the different notation $$f(x)=\Theta(g(x))$$ for Hardy's $$f(x)\asymp g(x)$$, and proposed a different definition for the Hardy and Littlewood Omega notation.

Two other symbols coined by Hardy were (in terms of the modern O notation)
 * $$ f \preccurlyeq g\iff f = O(g) $$  and   $$ f\prec g\iff f = o(g); $$

(Hardy however never defined or used the notation $$\prec\!\!\prec$$, nor $$\ll$$, as it has been sometimes reported). Hardy introduced the symbols $$\preccurlyeq $$ and $$\prec $$ (as well as the already mentioned other symbols) in his 1910 tract "Orders of Infinity", and made use of them only in three papers (1910–1913). In his nearly 400 remaining papers and books he consistently used the Landau symbols O and o.

Hardy's symbols $$\preccurlyeq$$ and $$\prec$$ (as well as $$\, \asymp\!\!\!\!\!\! - $$) are not used anymore. On the other hand, in the 1930s, the Russian number theorist Ivan Matveyevich Vinogradov  introduced his notation	$$\ll$$, which  has been increasingly used in number theory instead of  the $$O$$ notation. We have
 * $$ f\ll g \iff f = O(g), $$

and frequently both notations are used in the same paper.

The big-O originally stands for "order of" ("Ordnung", Bachmann 1894), and is thus a Latin letter. Neither Bachmann nor Landau ever call it "Omicron". The symbol was much later on (1976) viewed by Knuth as a capital omicron, probably in reference to his definition of the symbol Omega. The digit 0|zero should not be used.

title: Big O notation


text:
John of the Cross

John of the Cross (Juan de la Cruz; Ioannes a Cruce; born Juan de Yepes y Álvarez; 24 June 1542 – 14 December 1591) was a Spanish Catholic priest, mystic, and Carmelite friar of converso origin. He is a major figure of the Counter-Reformation in Spain, and he is one of the thirty-seven Doctors of the Church.

John of the Cross is known for his writings. He was mentored by and corresponded with the older Carmelite, Teresa of Ávila. Both his poetry and his studies on the development of the soul, particularly his Noche Obscura are considered the summit of mystical Spanish literature and among the greatest works of all Spanish literature. He was canonized by Pope Benedict XIII in 1726. In 1926, he was declared a Doctor of the Church by Pope Pius XI, and is also known as the "mystical doctor".

Early life and education

He was born Juan de Yepes y Álvarez at Fontiveros, Old Castile, into a converso family (descendants of Jewish converts to Catholicism) in Fontiveros, near Ávila, a town of around 2,000 people. His father, Gonzalo, was an accountant to richer relatives who were silk merchants. In 1529 Gonzalo married John's mother, Catalina, who was an orphan of a lower class; he was rejected by his family and forced to work with his wife as a weaver. John's father died in 1545, while John was still only around three years old. Two years later, John's older brother, Luis, died, probably as a result of malnourishment due to the poverty to which the family had been reduced. As a result, John's mother Catalina moved with John and his surviving brother Francisco, first to Arévalo in 1548, and then in 1551 to Medina del Campo, where she was able to find work.

In Medina, John entered a school for 160 poor children, mostly orphans, to receive a basic education, mainly in Christian doctrine. They were given some food, clothing, and lodging. While studying there, he was chosen to serve as an altar boy at a nearby monastery of Augustinian nuns. Growing up, John worked at a hospital and studied the humanities at a Jesuit school from 1559 to 1563. The Society of Jesus was at that time a new organisation, having been founded only a few years earlier by the Spaniard St. Ignatius of Loyola. In 1563 he entered the Carmelite Order, adopting the name John of St. Matthias.

In the following year (1564), he made his first vows and enrolled in Salamanca University, where he studied theology and philosophy. There he met Fray Luis de León, who taught biblical studies (Exegesis, Hebrew, and Aramaic) at the university.

Joining the Reform of Teresa of Ávila
John was ordained as a priest in 1567. He subsequently thought about joining the strict Carthusian Order, which appealed to him because of its practice of solitary and silent contemplation. His journey from Salamanca to Medina del Campo, probably in September 1567, became pivotal. In Medina he met the influential Carmelite nun, Teresa of Ávila. She was staying in Medina to found the second of her new convents. She immediately talked to him about her reformation projects for the Order: she was seeking to restore the purity of the Carmelite Order by reverting to the observance of its "Primitive Rule" of 1209, which had been relaxed by Pope Eugene IV in 1432.

Under the Rule, much of the day and night was to be divided between the recitation of the Liturgy of the Hours, study and devotional reading, the celebration of Mass and periods of solitude. In the case of friars, time was to be spent evangelizing the population around the monastery. There was to be total abstinence from meat and a lengthy period of fasting from the Feast of the Exaltation of the Cross (14 September) until Easter. There were to be long periods of silence, especially between Compline and Prime. Simpler, coarser, and shorter habits were to be adopted. There was also an injunction against wearing covered shoes (also previously mitigated in 1432). That particular observance distinguished the "discalced", i.e., barefoot, followers of Teresa from traditional Carmelites, and they would be formally recognized as the separate Order of Discalced Carmelites in 1580.

Teresa asked John to delay his entry into the Carthusian order and to follow her. Having spent a final year studying in Salamanca, in August 1568 John travelled with Teresa from Medina to Valladolid, where Teresa intended to found another convent. After a spell at Teresa's side in Valladolid, learning more about the new form of Carmelite life, in October 1568, John left Valladolid, accompanied by Friar Antonio de Jesús de Heredia, to found a new monastery for Carmelite friars, the first to follow Teresa's principles. They were given the use of a derelict house at Duruelo, which had been donated to Teresa. On 28 November 1568, the monastery was established, and on that same day, John changed his name to "John of the Cross".

Soon after, in June 1570, the friars found the house at Duruelo was too small, and so moved to the nearby town of Mancera de Abajo, midway between Ávila and Salamanca. John moved from the first community to set up a new community at Pastrana in October 1570, and then a further community at Alcalá de Henares, as a house for the academic training of the friars. In 1572 he arrived in Ávila, at Teresa's invitation. She had been appointed prioress of the Convent of the Incarnation there in 1571. John became the spiritual director and confessor of Teresa and the other 130 nuns there, as well as for a wide range of laypeople in the city. In 1574, John accompanied Teresa for the foundation of a new religious community in Segovia, returning to Ávila after staying there a week. Aside from the one trip, John seems to have remained in Ávila between 1572 and 1577.

At some time between 1574 and 1577, while praying in a loft overlooking the sanctuary in the Monastery of the Incarnation in Ávila, John had a vision of the crucified Christ, which led him to create his drawing of Christ "from above". In 1641, this drawing was placed in a small monstrance and kept in Ávila. This same drawing inspired the artist Salvador Dalí's 1951 work Christ of Saint John of the Cross.

Height of Carmelite tensions
The years 1575–77 saw a great increase in tensions among Spanish Carmelite friars over the reforms of Teresa and John. Since 1566 the reforms had been overseen by Canonical Visitors from the Dominican Order, with one appointed to Castile and a second to Andalusia. The Visitors had substantial powers: they could move members of religious communities from one house to another or from one province to the next. They could assist religious superiors in the discharge of their office, and could delegate superiors between the Dominican or Carmelite orders. In Castile, the Visitor was Pedro Fernández, who prudently balanced the interests of the Discalced Carmelites with those of the nuns and friars who did not desire reform.

In Andalusia to the south, the Visitor was Francisco Vargas, and tensions rose due to his clear preference for the Discalced friars. Vargas asked them to make foundations in various cities, in contradiction to the express orders from the Carmelite Prior General to curb expansion in Andalusia. As a result, a General Chapter of the Carmelite Order was convened at Piacenza in Italy in May 1576, out of concern that events in Spain were getting out of hand. It concluded by ordering the total suppression of the Discalced houses.

That measure was not immediately enforced. King Philip II of Spain was supportive of Teresa's reforms, and so was not immediately willing to grant the necessary permission to enforce the ordinance. The Discalced friars also found support from the papal nuncio to Spain,, Bishop of Padua, who still had ultimate power to visit and reform religious orders. When asked by the Discalced friars to intervene, Nuncio Ormaneto replaced Vargas as Visitor of the Carmelites in Andalusia with Jerónimo Gracián, a priest from the University of Alcalá, who was in fact a Discalced Carmelite friar himself. The nuncio's protection helped John avoid problems for a time. In January 1576, John was detained in Medina del Campo by traditional Carmelite friars, but through the nuncio's intervention, he was soon released. When Ormaneto died on 18 June 1577, John was left without protection, and the friars opposing his reforms regained the upper hand.

Foundations, imprisonment, torture and death
On the night of 2 December 1577, a group of Carmelites opposed to reform broke into John's dwelling in Ávila and took him prisoner. John had received an order from superiors, opposed to reform, to leave Ávila and return to his original house. John had refused on the basis that his reform work had been approved by the papal nuncio to Spain, a higher authority than these superiors. The Carmelites therefore took John captive. John was taken from Ávila to the Carmelite monastery in Toledo, at that time the order's leading monastery in Castile, with a community of 40 friars.

John was brought before a court of friars, accused of disobeying the ordinances of Piacenza. Despite his argument that he had not disobeyed the ordinances, he was sentenced to a term of imprisonment. He was jailed in a monastery where he was kept under a brutal regime that included public lashings before the community at least weekly, and severe isolation in a tiny stifling cell measuring barely 10 by 6 ft. Except when rarely permitted an oil lamp, he had to stand on a bench to read his breviary by the light through the hole into the adjoining room. He had no change of clothing and a penitential diet of water, bread and scraps of salt fish. During his imprisonment, he composed a great part of his most famous poem, Spiritual Canticle, as well as a few shorter poems. The paper was passed to him by the friar who guarded his cell. He managed to escape eight months later, on 15 August 1578, through a small window in a room adjoining his cell. (He had managed to pry open the hinges of the cell door earlier that day.)

After being nursed back to health, first by Teresa's nuns in Toledo, and then during six weeks at the Hospital of Santa Cruz, John continued with the reforms. In October 1578 he joined a meeting at Almodóvar del Campo of reform supporters, better known as the Discalced Carmelites. There, in part as a result of the opposition faced from other Carmelites, they decided to request from the Pope their formal separation from the rest of the Carmelite order.

At that meeting John was appointed superior of El Calvario, an isolated monastery of around thirty friars in the mountains about 6 mi away from Beas in Andalusia. During that time he befriended the nun Ana de Jesús, superior of the Discalced nuns at Beas, through his visits to the town every Saturday. While at El Calvario he composed the first version of his commentary on his poem The Spiritual Canticle, possibly at the request of the nuns in Beas.

In 1579 he moved to Baeza, a town of around 50,000 people, to serve as rector of a new college, the Colegio de San Basilio, for Discalced friars in Andalusia. It opened on 13 June 1579. He remained in post until 1582, spending much of his time as a spiritual director to the friars and townspeople.

1580 was a significant year in the resolution of disputes between the Carmelites. On 22 June, Pope Gregory XIII signed a decree, entitled Pia Consideratione, which authorised the separation of the old (later "calced") and the newly reformed, "Discalced" Carmelites. The Dominican friar Juan Velázquez de las Cuevas was appointed to oversee the decision. At the first General Chapter of the Discalced Carmelites, in Alcalá de Henares on 3 March 1581, John of the Cross was elected one of the "Definitors" of the community, and wrote a constitution for them. By the time of the Provincial Chapter at Alcalá in 1581, there were 22 houses, some 300 friars and 200 nuns among the Discalced Carmelites.

In November 1581, John was sent by Teresa to help Ana de Jesús to found a convent in Granada. Arriving in January 1582, she set up a convent, while John stayed in the monastery of Los Mártires, near the Alhambra, becoming its prior in March 1582. While there, he learned of Teresa's death in October of that year.

In February 1585, John travelled to Málaga where he established a convent for Discalced nuns. In May 1585, at the General Chapter of the Discalced Carmelites in Lisbon, John was elected Vicar Provincial of Andalusia, a post which required him to travel frequently, making annual visitations to the houses of friars and nuns in Andalusia. During this time he founded seven new monasteries in the region, and is estimated to have travelled around 25,000 km.

In June 1588, he was elected third Councillor to the Vicar General for the Discalced Carmelites, Father Nicolas Doria. To fulfill this role, he had to return to Segovia in Castile, where he also took on the role of prior of the monastery. After disagreeing in 1590–1 with some of Doria's remodelling of the leadership of the Discalced Carmelite Order, John was removed from his post in Segovia, and sent by Doria in June 1591 to an isolated monastery in Andalusia called La Peñuela. There he fell ill, and travelled to the monastery at Úbeda for treatment. His condition worsened, however, and he died there of erysipelas on 14 December 1591.

Veneration
The morning after John's death huge numbers of townspeople in Úbeda entered the monastery to view his body; in the crush, many were able to take home bits of his habit. He was initially buried at Úbeda, but, at the request of the monastery in Segovia, his body was secretly moved there in 1593. The people of Úbeda, however, unhappy at this change, sent a representative to petition the pope to move the body back to its original resting place. Pope Clement VIII, impressed by the petition, issued a Brief on 15 October 1596 ordering the return of the body to Úbeda. Eventually, in a compromise, the superiors of the Discalced Carmelites decided that the monastery at Úbeda would receive one leg and one arm of the corpse from Segovia (the monastery at Úbeda had already kept one leg in 1593, and the other arm had been removed as the corpse passed through Madrid in 1593, to form a relic there). A hand and a leg remain visible in a reliquary at the Oratory of San Juan de la Cruz in Úbeda, a monastery built in 1627 though connected to the original Discalced monastery in the town founded in 1587.

The head and torso were retained by the monastery at Segovia. They were venerated until 1647, when on orders from Rome designed to prevent the veneration of remains without official approval, the remains were buried in the ground. In the 1930s they were disinterred, and are now sited in a side chapel in a marble case above a special altar.

Proceedings to beatify John began between 1614 and 1616. He was eventually beatified in 1675 by Pope Clement X, and was canonized by Benedict XIII in 1726. When his feast day was added to the General Roman Calendar in 1738, it was assigned to 24 November, since his date of death was impeded by the then-existing octave of the Feast of the Immaculate Conception. This obstacle was removed in 1955 and in 1969 Pope Paul VI moved it to the dies natalis (birthday to heaven) of John, 14 December. The Church of England and the Episcopal Church honor him on the same date. In 1926, he was declared a Doctor of the Church by Pope Pius XI after the definitive consultation of Reginald Garrigou-Lagrange OP, professor of philosophy and theology at the Pontifical University of Saint Thomas Aquinas, Angelicum in Rome.

Literary works
John of the Cross is considered one of the foremost poets in Spanish. Although his complete poems add up to fewer than 2,500 verses, two of them, the Spiritual Canticle and the Dark Night of the Soul, are widely considered masterpieces of Spanish poetry, both for their formal style and their rich symbolism and imagery. His theological works often consist of commentaries on the poems. All the works were written between 1578 and his death in 1591.

The Spiritual Canticle is an eclogue in which the bride, representing the soul, searches for the bridegroom, representing Jesus Christ, and is anxious at having lost him. Both are filled with joy upon reuniting. It can be seen as a free-form Spanish version of the Song of Songs at a time when vernacular translations of the Bible were forbidden. The first 31 stanzas of the poem were composed in 1578 while John was imprisoned in Toledo. After his escape it was read by the nuns at Beas, who made copies of the stanzas. Over the following years, John added further lines. Today, two versions exist: one with 39 stanzas and one with 40 with some of the stanzas ordered differently. The first redaction of the commentary on the poem was written in 1584, at the request of Madre Ana de Jesús, when she was prioress of the Discalced Carmelite nuns in Granada. A second edition, which contains more detail, was written in 1585–6.

The Dark Night, from which the phrase Dark Night of the Soul takes its name, narrates the journey of the soul from its bodily home to union with God. It happens during the "dark", which represents the hardships and difficulties met in detachment from the world and reaching the light of the union with the Creator. There are several steps during the state of darkness, which are described in successive stanzas. The main idea behind the poem is the painful experience required to attain spiritual maturity and union with God. The poem was likely written in 1578 or 1579. In 1584–5, John wrote a commentary on the first two stanzas and on the first line of the third stanza.

The Ascent of Mount Carmel is a more systematic study of the ascetical endeavour of a soul seeking perfect union with God and the mystical events encountered along the way. Although it begins as a commentary on The Dark Night, after the first two stanzas of the poem, it rapidly diverts into a full treatise. It was composed some time between 1581 and 1585.

A four-stanza work, Living Flame of Love, describes a greater intimacy, as the soul responds to God's love. It was written in a first version at Granada between 1585 and 1586, apparently in two weeks, and in a mostly identical second version at La Peñuela in 1591.

These, together with his Dichos de Luz y Amor or "Sayings of Light and Love" along with Teresa's own writings, are the most important mystical works in Spanish, and have deeply influenced later spiritual writers across the world. They include: T. S. Eliot, Thérèse de Lisieux, Edith Stein (Teresa Benedicta of the Cross) and Thomas Merton. John is said to have also influenced philosophers (Jacques Maritain), theologians (Hans Urs von Balthasar), pacifists (Dorothy Day, Daniel Berrigan and Philip Berrigan) and artists (Salvador Dalí). Pope John Paul II wrote his theological dissertation on the mystical theology of John of the Cross.

Editions of his works
His writings were first published in 1618 by Diego de Salablanca. The numerical divisions in the work, still used by modern editions of the text, were introduced by Salablanca (they were not in John's original writings) to help make the work more manageable for the reader. This edition does not contain the Spiritual Canticle, however, and also omits or adapts certain passages, perhaps for fear of falling foul of the Inquisition.

The Spiritual Canticle was first included in the 1630 edition, produced by Fray Jeronimo de San José, at Madrid. This edition was largely followed by later editors, although editions in the seventeenth and eighteenth centuries gradually included a few more poems and letters.

The first French edition was published in Paris in 1622, and the first Castilian edition in 1627 in Brussels.

A critical edition of John's works in English was published by E. Allison Peers in 1935.

Intellectual influences
The influences on John's writing are subject to an ongoing debate. It is widely acknowledged that at Salamanca university there would have existed a range of intellectual positions. In John's time they included the influences of Thomas Aquinas, of Scotus and of Durandus. It is often assumed that John would have absorbed the thought of Aquinas, to explain the scholastic framework of his writings.

However, the belief that John was taught at both the Carmelite College of San Andrès and at the University of Salamanca has been challenged. Bezares calls into question whether John even studied theology at the University of Salamanca. The philosophy courses John probably took in logic, natural and moral philosophy, can be reconstructed, but Bezares argues that John in fact abandoned his studies at Salamanca in 1568 to join Teresa, rather than graduating. In the first biography of John, published in 1628, it is claimed, on the basis of information from John's fellow students, that he in 1567 made a special study of mystical writers, in particular of Pseudo-Dionysius and Pope Gregory I. There is little consensus from John's early years or potential influences.

Scripture
John was influenced heavily by the Bible. Scriptural images are common in both his poems and prose. In total, there are 1,583 explicit and 115 implicit quotations from the Bible in his works. The influence of the Song of Songs on John's Spiritual Canticle has often been noted, both in terms of the structure of the poem, with its dialogue between two lovers, the account of their difficulties in meeting each other and the "offstage chorus" that comments on the action, and also in terms of the imagery, for example, of pomegranates, wine cellar, turtle dove and lilies, which echoes that of the Song of Songs.

In addition, John shows at occasional points the influence of the Divine Office. This demonstrates how John, steeped in the language and rituals of the Church, drew at times on the phrases and language here.

Pseudo-Dionysius
It has rarely been disputed that the overall structure of John's mystical theology, and his language of the union of the soul with God, is influenced by the pseudo-Dionysian tradition. However, it has not been clear whether John might have had direct access to the writings of Pseudo-Dionysius, or whether this influence may have been mediated through various later authors.

Medieval mystics
It is widely acknowledged that John may have been influenced by the writings of other medieval mystics, though there is debate about the exact thought which may have influenced him, and about how he might have been exposed to their ideas.

The possibility of influence by the so-called "Rhineland mystics" such as Meister Eckhart, Johannes Tauler, Henry Suso and John of Ruysbroeck has also been mooted by many authors.

Secular Spanish poetry
A strong argument can also be made for contemporary Spanish literary influences on John. This case was first made in detail by Dámaso Alonso, who believed that as well as drawing from scripture, John was transforming non-religious, profane themes, derived from popular songs (romanceros) into religious poetry.

Islamic influence
A controversial theory on the origins of John's mystical imagery is that he may have been influenced by Islamic sources. This was first proposed in detail by Miguel Asín Palacios and has been most recently put forward by the Puerto Rican scholar Luce López-Baralt. Arguing that John was influenced by Islamic sources on the peninsula, she traces Islamic antecedents of the images of the "dark night", the "solitary bird" of the Spiritual Canticle, wine and mystical intoxication (the Spiritual Canticle), lamps of fire (the Living Flame). However, Peter Tyler concludes, there "are sufficient Christian medieval antecedents for many of the metaphors John employs to suggest we should look for Christian sources rather than Muslim sources". As José Nieto indicates, in trying to locate a link between Spanish Christian mysticism and Islamic mysticism, it might make more sense to refer to the common Neo-Platonic tradition and mystical experiences of both, rather than seek direct influence.

Books

 * John of the Cross, Dark Night of the Soul, London, 2012. limovia.net ISBN 978-1-78336-005-5
 * John of the Cross, Ascent of Mount Carmel, London, 2012. limovia.net ISBN 978-1-78336-009-3
 * John of the Cross, Spiritual Canticle of the Soul and the Bridegroom Christ, London, 2012. limovia.net ISBN 978-1-78336-014-7
 * The Dark Night: A Masterpiece in the Literature of Mysticism (Translated and Edited by E. Allison Peers), Doubleday, 1959. ISBN 978-0-385-02930-8
 * The Poems of Saint John of the Cross (English Versions and Introduction by Willis Barnstone), Indiana University Press, 1968, revised 2nd ed. New Directions, 1972. ISBN 0-8112-0449-9
 * The Dark Night, St. John of the Cross (Translated by Mirabai Starr), Riverhead Books, New York, 2002, ISBN 1-57322-974-1
 * Poems of St John of The Cross (Translated and Introduction by Kathleen Jones), Burns and Oates, Tunbridge Wells, Kent, UK, 1993, ISBN 0-86012-210-7
 * The Collected Works of St John of the Cross (Eds. K. Kavanaugh and O. Rodriguez), Institute of Carmelite Studies, Washington DC, revised edition, 1991, ISBN 0-935216-14-6
 * St. John of the Cross: His Prophetic Mysticism in Sixteenth-Century Spain by Cristobal Serran-Pagan

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: John of the Cross


text:
Robert of Ketton

Robert of Ketton, known in Latin as Rodbertus Ketenensis ( 1141–1157), was an English astronomer, translator, priest and diplomat active in Spain. He translated several works of Arabic into Latin, including the first translation of the Quran into any Western language. Between 1144 and 1157 he held an archdeaconry in the diocese of Pamplona. In the past he has been confounded with Robert of Chester (Latin Robertus Castrensis), another English translator active in Spain in the mid-twelfth century; and at least one modern scholar believes they are the same person.

Robert's byname, Ketenensis or on one occasion de Ketene, is usually taken to refer to Ketton, a village in Rutland, a few miles from Stamford, Lincolnshire. It was probably Robert's birthplace. This nickname was never used in official documents associated with Pamplona, where he was always simply "Master Robert" (magister Rodbertus), indicating that he had a master of arts degree. The identification of the translator known as Robert of Ketton and the archdeacon known as Master Robert is provided by a letter of Peter the Venerable, abbot of Cluny. In the spring or summer of 1144, when Peter sent some of Robert's translations to Bernard of Clairvaux. In the accompanying letter he named the translator as "Robert of Ketton from England, who is now archdeacon of the church of Pamplona" (Roberto Ketenensi de Anglia, qui nunc Pampilonensis ecclesiae archidiaconus est).

Translations
Prior to 1141, Robert and Hermann of Carinthia were engaged in a project of translating Arabic texts into Latin for their own use and education. Richard Hakluyt surmised that the two men had travelled in Arabic-speaking countries. Only one product of Robert from this early collaboration is known or has survived. On Hermann's request, Robert translated al-Kindi's Astrological Judgements, under the Latin title Judicia. (Many later manuscripts misattribute it to the astronomer Robertus Anglicus.) In the preface to this translation, he explains that his interest is in geometry and astronomy, but that he is undertaking an astrological work for the sake of his friendship with Hermann. Their real plan, he says, is to work through Euclid's Elements and Theodosius's Spherics in order to be capable of understanding Ptolemy's Almagest. All of these texts would have been available to them only in Arabic at that time.

It has been suggested that one other text that survives might be Robert's work from his and Hermann's private collaboration: a translation of Euclid's Elements known as "Adelard II", which is usually attributed to Adelard of Bath and sometimes to Robert of Chester. It was the most popular of several Latin translations of Euclid from the twelfth century. In his translation of Ptolemy's Planisphere of 1143, Hermann also mentions that Robert gave him the astronomical tables of al-Battani, perhaps in translation.

In 1141, Robert and Hermann met Abbot Peter the Venerable on the banks of the Ebro, probably at Logroño, and he convinced them to translate some Islamic texts for his collection, which has become known as the Toledan Collection. For this project, Robert translated a history of the early Caliphate under the title Chronica mendosa Saracenorum (Lying Chronicle of the Saracens) and the Quran itself under the title Lex Mahumet pseudoprophete (Law of the False Prophet Muhammad). For the latter work he was assisted by a certain Muhammad. His translation is very free and he does not subdivide the text according to the suras. The entire Toledan Collection was printed by the Protestant printer Theodore Bibliander at Basel in 1543.

As late as 1143, Robert still had in mind his and Hermann's pet project of astronomical translations, for he wrote a letter to Peter the Venerable promising "a celestial gift which embraces within itself the whole of science … revealing most accurately, according to number, proportion and measure, all the celestial circles and their quantities, orders and conditions, and, finally, all the various movements of the stars, and their effects and natures."

Ecclesiastical career
Robert's career in the church began after his career as a translator had ended. (Perhaps he received his benefice as a reward for his work.) He was an archdeacon at Pamplona from at least 1144—and probably shortly before that—until 1157, when he was transferred to a canonry of Tudela. His presence at Pamplona is known from documents of 1145, 1147, 1149 and 1151. He was in Barcelona on official business in 1152. He seems to have held the archdeaconry of Valdonsella, which included the town of Uncastillo. Since the Kingdom of Navarre regained its independence in 1134, this lay on the border with and was disputed by the Kingdom of Aragon. Robert served King García Ramírez of Navarre (whose grandfather, Sancho Garcés, was lord of Uncastillo) as a diplomat, even drawing up the peace treaty signed with Raymond Berengar IV, regent of Aragon, on 1 July 1149. For this effort on behalf of peace, he was commended by Pope Eugenius III.

In 1151, Robert's bishop, Lope de Artajona, sent him as his delegate to a conference to resolve the disputed boundary between the dioceses of Pamplona and Zaragoza. Later, Robert led some of the Pamplonese clergy into rebellion against Lope. Their dispute was for a time patched up, but when Lope came into conflict with King Sancho VI, Robert joined the king's side. It was probably through the king that he obtained the canonry in Tudela after his archdeaconry had become untenable. There is no record of him after 1157. Charles Burnett notes that "Robert's education fit him well for the roles of diplomat, royal adviser and redactor of official documents."

title: Robert of Ketton


text:
Cyclotron

A cyclotron is a type of particle accelerator invented by Ernest Lawrence in 1929–1930 at the University of California, Berkeley, and patented in 1932. A cyclotron accelerates charged particles outwards from the center of a flat cylindrical vacuum chamber along a spiral path. The particles are held to a spiral trajectory by a static magnetic field and accelerated by a rapidly varying electric field. Lawrence was awarded the 1939 Nobel Prize in Physics for this invention.

The cyclotron was the first "cyclical" accelerator. The primary accelerators before the development of the cyclotron were electrostatic accelerators, such as the Cockcroft–Walton generator and the Van de Graaff generator. In these accelerators, particles would cross an accelerating electric field only once. Thus, the energy gained by the particles was limited by the maximum electrical potential that could be achieved across the accelerating region. This potential was in turn limited by electrostatic breakdown to a few million volts. In a cyclotron, by contrast, the particles encounter the accelerating region many times by following a spiral path, so the output energy can be many times the energy gained in a single accelerating step.

Cyclotrons were the most powerful particle accelerator technology until the 1950s, when they were surpassed by the synchrotron. Nonetheless, they are still widely used to produce particle beams for nuclear medicine and basic research. As of 2020, close to 1,500 cyclotrons were in use worldwide for the production of radionuclides for nuclear medicine. In addition, cyclotrons can be used for particle therapy, where particle beams are directly applied to patients.

History

In 1927, while a student at Kiel, German physicist Max Steenbeck was the first to formulate the concept of the cyclotron, but he was discouraged from pursuing the idea further. In late 1928 and early 1929, Hungarian physicist Leo Szilárd filed patent applications in Germany for the linear accelerator, cyclotron, and betatron. In these applications, Szilárd became the first person to discuss the resonance condition (what is now called the cyclotron frequency) for a circular accelerating apparatus. However, neither Steenbeck's ideas nor Szilard's patent applications were ever published and therefore did not contribute to the development of the cyclotron. Several months later, in the early summer of 1929, Ernest Lawrence independently conceived the cyclotron concept after reading a paper by Rolf Widerøe describing a drift tube accelerator. He published a paper in Science in 1930 (the first published description of the cyclotron concept), after a student of his built a crude model in April of that year. He patented the device in 1932.

To construct the first such device, Lawrence used large electromagnets recycled from obsolete arc converters provided by the Federal Telegraph Company. He was assisted by a graduate student, M. Stanley Livingston. Their first working cyclotron became operational in January 1931. This machine had a diameter of 4.5 in, and accelerated protons to an energy up to 80 keV.

At the Radiation Laboratory on the campus of the University of California, Berkeley (now the Lawrence Berkeley National Laboratory), Lawrence and his collaborators went on to construct a series of cyclotrons which were the most powerful accelerators in the world at the time; a 27 in 4.8 MeV machine (1932), a 37 in 8 MeV machine (1937), and a 60 in 16 MeV machine (1939). Lawrence received the 1939 Nobel Prize in Physics for the invention and development of the cyclotron and for results obtained with it.

The first European cyclotron was constructed in the Soviet Union in the physics department of the V.G. Khlopin Radium Institute in Leningrad, headed by. This Leningrad instrument was first proposed in 1932 by George Gamow and and was installed and became operative by 1937.

Two cyclotrons were built in Nazi Germany. The first was constructed in 1937, in Otto Hahn's laboratory at the Kaiser Wilhelm Institute in Berlin, and was also used by Rudolf Fleischmann. It was the first cyclotron with a Greinacher multiplier to increase the voltage to 2.8 MV and 3 mA current. A second cyclotron was built in Heidelberg under the supervision of Walther Bothe and Wolfgang Gentner, with support from the Heereswaffenamt, and became operative in 1943.

By the late 1930s it had become clear that there was a practical limit on the beam energy that could be achieved with the traditional cyclotron design, due to the effects of special relativity. As particles reach relativistic speeds, their effective mass increases, which causes the resonant frequency for a given magnetic field to change. To address this issue and reach higher beam energies using cyclotrons, two primary approaches were taken, synchrocyclotrons (which hold the magnetic field constant, but decrease the accelerating frequency) and isochronous cyclotrons (which hold the accelerating frequency constant, but alter the magnetic field).

Lawrence's team built one of the first synchrocyclotrons in 1946. This 184 in machine eventually achieved a maximum beam energy of 350 MeV for protons. However, synchrocyclotrons suffer from low beam intensities (< 1 μA), and must be operated in a "pulsed" mode, further decreasing the available total beam. As such, they were quickly overtaken in popularity by isochronous cyclotrons.

The first isochronous cyclotron (other than classified prototypes) was built by F. Heyn and K.T. Khoe in Delft, the Netherlands, in 1956. Early isochronous cyclotrons were limited to energies of ~50 MeV per nucleon, but as manufacturing and design techniques gradually improved, the construction of "spiral-sector" cyclotrons allowed the acceleration and control of more powerful beams. Later developments included the use of more powerful superconducting magnets and the separation of the magnets into discrete sectors, as opposed to a single large magnet.

Cyclotron principle
In a particle accelerator, charged particles are accelerated by applying an electric field across a gap. The force on a particle crossing this gap is given by the Lorentz force law:

$$\mathbf{F} = q  [\mathbf{E} + (\mathbf{v} \times \mathbf{B})]$$

where $q$ is the charge on the particle, $E$ is the electric field, $v$ is the particle velocity, and $B$ is the magnetic flux density. It is not possible to accelerate particles using only a static magnetic field, as the magnetic force always acts perpendicularly to the direction of motion, and therefore can only change the direction of the particle, not the speed.

In practice, the magnitude of an unchanging electric field which can be applied across a gap is limited by the need to avoid electrostatic breakdown. As such, modern particle accelerators use alternating (radio frequency) electric fields for acceleration. Since an alternating field across a gap only provides an acceleration in the forward direction for a portion of its cycle, particles in RF accelerators travel in bunches, rather than a continuous stream. In a linear particle accelerator, in order for a bunch to "see" a forward voltage every time it crosses a gap, the gaps must be placed further and further apart, in order to compensate for the increasing speed of the particle.

A cyclotron, by contrast, uses a magnetic field to bend the particle trajectories into a spiral, thus allowing the same gap to be used many times to accelerate a single bunch. As the bunch spirals outward, the increasing distance between transits of the gap is exactly balanced by the increase in speed, so a bunch will reach the gap at the same point in the RF cycle every time.

The frequency at which a particle will orbit in a perpendicular magnetic field is known as the cyclotron frequency, and depends, in the non-relativistic case, solely on the charge and mass of the particle, and the strength of the magnetic field:

$$f = \frac{qB}{2\pi m}$$

where $f$ is the (linear) frequency, $q$ is the charge of the particle, $B$ is the magnitude of the magnetic field that is perpendicular to the plane in which the particle is travelling, and $m$ is the particle mass. The property that the frequency is independent of particle velocity is what allows a single, fixed gap to be used to accelerate a particle travelling in a spiral.

Particle energy
Each time a particle crosses the accelerating gap in a cyclotron, it is given an accelerating force by the electric field across the gap, and the total particle energy gain can be calculated by multiplying the increase per crossing by the number of times the particle crosses the gap.

However, given the typically high number of revolutions, it is usually simpler to estimate the energy by combining the equation for frequency in circular motion:

$$f = \frac{v}{2 \pi r}$$

with the cyclotron frequency equation to yield:

$$v = \frac{q B r}{m}$$

The kinetic energy for particles with speed $v$ is therefore given by:

$$E = \frac{1}{2}m v^2 = \frac{q^2 B^2 r^2}{2 m}$$

where $r$ is the radius at which the energy is to be determined. The limit on the beam energy which can be produced by a given cyclotron thus depends on the maximum radius which can be reached by the magnetic field and the accelerating structures, and on the maximum strength of the magnetic field which can be achieved.

K-factor
In the nonrelativistic approximation, the maximum kinetic energy per atomic mass for a given cyclotron is given by:

$$\frac{T}{A} = \frac{(e B r_{\max})^2}{2 m_a}\left(\frac{Q}{A}\right)^2 = K \left(\frac{Q}{A}\right)^2$$

where $$e$$ is the elementary charge, $$B$$ is the strength of the magnet, $$r_{\max}$$ is the maximum radius of the beam, $$m_a$$ is an atomic mass unit, $$Q$$ is the charge of the beam particles, and $$A$$ is the atomic mass of the beam particles. The value of K

$$K = \frac{(e B r_{\max})^2}{2 m_a}$$

is known as the "K-factor", and is used to characterize the maximum kinetic beam energy of protons (quoted in MeV). It represents the theoretical maximum energy of protons (with Q and A equal to 1) accelerated in a given machine.

Particle trajectory

While the trajectory followed by a particle in the cyclotron is conventionally referred to as a "spiral", it is more accurately described as a series of arcs of constant radius. The particle speed, and therefore orbital radius, only increases at the accelerating gaps. Away from those regions, the particle will orbit (to a first approximation) at a fixed radius.

Assuming a uniform energy gain per orbit (which is only valid in the non-relativistic case), the average orbit may be approximated by a simple spiral. If the energy gain per turn is given by $ΔE$, the particle energy after $n$ turns will be: $$E(n) = n \Delta E$$ Combining this with the non-relativistic equation for the kinetic energy of a particle in a cyclotron gives: $$r(n) = {\sqrt{2 m \Delta E} \over q B} \sqrt{n}$$ This is the equation of a Fermat spiral.

Stability and focusing
As a particle bunch travels around a cyclotron, two effects tend to make its particles spread out. The first is simply the particles injected from the ion source having some initial spread of positions and velocities. This spread tends to get amplified over time, making the particles move away from the bunch center. The second is the mutual repulsion of the beam particles due to their electrostatic charges. Keeping the particles focused for acceleration requires confining the particles to the plane of acceleration (in-plane or "vertical" focusing), preventing them from moving inward or outward from their correct orbit ("horizontal" focusing), and keeping them synchronized with the accelerating RF field cycle (longitudinal focusing).

Transverse stability and focusing
The in-plane or "vertical" focusing is typically achieved by varying the magnetic field around the orbit, i.e. with azimuth. A cyclotron using this focusing method is thus called an azimuthally-varying field (AVF) cyclotron. The variation in field strength is provided by shaping the steel poles of the magnet into sectors which can have a shape reminiscent of a spiral and also have a larger area towards the outer edge of the cyclotron to improve the vertical focus of the particle beam. This solution for focusing the particle beam was proposed by L. H. Thomas in 1938 and almost all modern cyclotrons use azimuthally-varying fields.

The "horizontal" focusing happens as a natural result of cyclotron motion. Since for identical particles travelling perpendicularly to a constant magnetic field the trajectory curvature radius is only a function of their speed, all particles with the same speed will travel in circular orbits of the same radius, and a particle with a slightly incorrect trajectory will simply travel in a circle with a slightly offset center. Relative to a particle with a centered orbit, such a particle will appear to undergo a horizontal oscillation relative to the centered particle. This oscillation is stable for particles with a small deviation from the reference energy.

Longitudinal stability
The instantaneous level of synchronization between a particle and the RF field is expressed by phase difference between the RF field and the particle. In the first harmonic mode (i.e. particles make one revolution per RF cycle) it is the difference between the instantaneous phase of the RF field and the instantaneous azimuth of the particle. Fastest acceleration is achieved when the phase difference equals 90° (modulo360°). Poor synchronization, i.e. phase difference far from this value, leads to the particle being accelerated slowly or even decelerated (outside of the 0–180° range).

As the time taken by a particle to complete an orbit depends only on particle's type, magnetic field (which may vary with the radius), and Lorentz factor (see ), cyclotrons have no longitudinal focusing mechanism which would keep the particles synchronized to the RF field. The phase difference, that the particle had at the moment of its injection into the cyclotron, is preserved throughout the acceleration process, but errors from imperfect match between the RF field frequency and the cyclotron frequency at a given radius accumulate on top of it. Failure of the particle to be injected with phase difference within about ±20° from the optimum may make its acceleration too slow and its stay in the cyclotron too long. As a consequence, half-way through the process the phase difference escapes the 0–180° range, the acceleration turns into deceleration, and the particle fails to reach the target energy. Grouping of the particles into correctly synchronized bunches before their injection into the cyclotron thus greatly increases the injection efficiency.

Relativistic considerations
In the non-relativistic approximation, the cyclotron frequency does not depend upon the particle's speed or the radius of the particle's orbit. As the beam spirals outward, the rotation frequency stays constant, and the beam continues to accelerate as it travels a greater distance in the same time period. In contrast to this approximation, as particles approach the speed of light, the cyclotron frequency decreases due to the change in relativistic mass. This change is proportional to the particle's Lorentz factor.

The relativistic mass can be written as:

$$m = \frac{m_0}{\sqrt{1-\left(\frac{v}{c}\right)^2}} = \frac{m_0}{\sqrt{1-\beta^2}} = \gamma {m_0},$$

where:
 * $$m_0$$ is the particle rest mass,
 * $$\beta = \frac{v}{c}$$ is the relative velocity, and
 * $$\gamma=\frac{1}{\sqrt{1-\beta^2}}=\frac{1}{\sqrt{1-\left(\frac{v}{c}\right)^2}}$$ is the Lorentz factor.

Substituting this into the equations for cyclotron frequency and angular frequency gives:

$$\begin{align} f & = \frac{q B}{2\pi \gamma m_0} \\[6pt] \omega & = \frac{q B}{\gamma m_0} \end{align}$$

The gyroradius for a particle moving in a static magnetic field is then given by: $$r = \frac{\gamma \beta m_0 c}{q B} = \frac{\gamma m_0 v}{q B} = \frac{m_0}{q B \sqrt{v^{-2} - c^{-2}}}$$

Expressing the speed in this equation in terms of frequency and radius $$v = 2\pi f r$$ yields the connection between the magnetic field strength, frequency, and radius: $$\left(\frac{1}{2\pi f}\right)^2 = \left(\frac{m_0}{q B}\right)^2 + \left(\frac{r}{c}\right)^2$$

Synchrocyclotron
Since $$\gamma$$ increases as the particle reaches relativistic velocities, acceleration of relativistic particles requires modification of the cyclotron to ensure the particle crosses the gap at the same point in each RF cycle. If the frequency of the accelerating electric field is varied while the magnetic field is held constant, this leads to the synchrocyclotron.

In this type of cyclotron, the accelerating frequency is varied as a function of particle orbit radius such that:

$$f(r) = \frac{1}{2\pi \sqrt{\left(\frac{m_0}{q B}\right)^2 + \left(\frac{r}{c}\right)^2}}$$

The decrease in accelerating frequency is tuned to match the increase in gamma for a constant magnetic field.

Isochronous cyclotron

If instead the magnetic field is varied with radius while the frequency of the accelerating field is held constant, this leads to the isochronous cyclotron.

$$B(r) = \frac{m_0}{q \sqrt{\left(\frac{1}{2\pi f}\right)^2 - \left(\frac{r}{c}\right)^2}}$$

Keeping the frequency constant allows isochronous cyclotrons to operate in a continuous mode, which makes them capable of producing much greater beam current than synchrocyclotrons. On the other hand, as precise matching of the orbital frequency to the accelerating field frequency is the responsibility of the magnetic field variation with radius, the variation must be precisely tuned.

Fixed-field alternating gradient accelerator (FFA)
An approach which combines static magnetic fields (as in the synchrocyclotron) and alternating gradient focusing (as in a synchrotron) is the fixed-field alternating gradient accelerator (FFA). In an isochronous cyclotron, the magnetic field is shaped by using precisely machined steel magnet poles. This variation provides a focusing effect as the particles cross the edges of the poles. In an FFA, separate magnets with alternating directions are used to focus the beam using the principle of strong focusing. The field of the focusing and bending magnets in an FFA is not varied over time, so the beam chamber must still be wide enough to accommodate a changing beam radius within the field of the focusing magnets as the beam accelerates.

Cyclotron types
There are a number of basic types of cyclotron:

Classical cyclotron: The earliest and simplest cyclotron. Classical cyclotrons have uniform magnetic fields and a constant accelerating frequency. They are limited to nonrelativistic particle velocities (the output energy small compared to the particle's rest energy), and have no active focusing to keep the beam aligned in the plane of acceleration. Synchrocyclotron: The synchrocyclotron extended the energy of the cyclotron into the relativistic regime by decreasing the frequency of the accelerating field as the orbit of the particles increased to keep it synchronized with the particle revolution frequency. Because this requires pulsed operation, the integrated total beam current was low compared to the classical cyclotron. In terms of beam energy, these were the most powerful accelerators during the 1950s, before the development of the synchrotron. Isochronous cyclotron (isocyclotron): These cyclotrons extend output energy into the relativistic regime by altering the magnetic field to compensate for the change in cyclotron frequency as the particles reached relativistic speed. They use specially shaped magnet pole pieces that are wider near the outer diameter of the cyclotron to create a nonuniform magnetic field stronger in peripheral regions. Most modern cyclotrons are of this type. The pole pieces can also be shaped to cause the beam to keep the particles focused in the acceleration plane as the orbit. This is known as "sector focusing" or "azimuthally-varying field focusing", and uses the principle of alternating-gradient focusing. Separated sector cyclotron: Separated sector cyclotrons are machines in which the magnet is in separate sections, separated by gaps without field. Superconducting cyclotron: "Superconducting" in the cyclotron context refers to the type of magnet used to bend the particle orbits into a spiral. Superconducting magnets can produce substantially higher fields in the same area than normal conducting magnets, allowing for more compact, powerful machines. The first superconducting cyclotron was the K500 at the Michigan State University, which came online in 1981.

Beam types
The particles for cyclotron beams are produced in ion sources of various types.

Proton beams: The simplest type of cyclotron beam, proton beams are typically created by ionizing hydrogen gas. H− beams: Accelerating negative hydrogen ions simplifies extracting the beam from the machine. At the radius corresponding to the desired beam energy, a metal foil is used to strip the electrons from the H− ions, transforming them into positively charged H+ ions. The change in polarity causes the beam to be deflected in the opposite direction by the magnetic field, allowing the beam to be transported out of the machine. Heavy ion beams: Beams of particles heavier than hydrogen are referred to as heavy ion beams, and can range from deuterium nuclei (one proton and one neutron) up to uranium nuclei. The increase in energy required to accelerate heavier particles is balanced by stripping more electrons from the atom to increase the electric charge of the particles, thus increasing acceleration efficiency.

Target types
To make use of the cyclotron beam, it must be directed to a target.

Internal targets: The simplest way to strike a target with a cyclotron beam is to insert it directly into the path of the beam in the cyclotron. Internal targets have the disadvantage that they must be compact enough to fit within the cyclotron beam chamber, making them impractical for many medical and research uses. External targets: While extracting a beam from a cyclotron to impinge on an external target is more complicated than using an internal target, it allows for greater control of the placement and focus of the beam, and much more flexibility in the types of targets to which the beam can be directed.

Basic research
For several decades, cyclotrons were the best source of high-energy beams for nuclear physics experiments. With the advent of strong focusing synchrotrons, cyclotrons were supplanted as the accelerators capable of producing the highest energies. However, due to their compactness, and therefore lower expense compared to high energy synchrotrons, cyclotrons are still used to create beams for research where the primary consideration is not achieving the maximum possible energy. Cyclotron based nuclear physics experiments are used to measure basic properties of isotopes (particularly short lived radioactive isotopes) including half life, mass, interaction cross sections, and decay schemes.

Radioisotope production
Cyclotron beams can be used to bombard other atoms to produce short-lived isotopes with a variety of medical uses, including medical imaging and radiotherapy. Positron and gamma emitting isotopes, such as fluorine-18, carbon-11, and technetium-99m are used for PET and SPECT imaging. While cyclotron produced radioisotopes are widely used for diagnostic purposes, therapeutic uses are still largely in development. Proposed isotopes include astatine-211, palladium-103, rhenium-186, and bromine-77, among others.

Beam therapy
The first suggestion that energetic protons could be an effective treatment method was made by Robert R. Wilson in a paper published in 1946 while he was involved in the design of the Harvard Cyclotron Laboratory.

Beams from cyclotrons can be used in particle therapy to treat cancer. Ion beams from cyclotrons can be used, as in proton therapy, to penetrate the body and kill tumors by radiation damage, while minimizing damage to healthy tissue along their path.

As of 2020, there were approximately 80 facilities worldwide for radiotherapy using beams of protons and heavy ions, consisting of a mixture of cyclotrons and synchrotrons. Cyclotrons are primarily used for proton beams, while synchrotrons are used to produce heavier ions.

Advantages and limitations

The most obvious advantage of a cyclotron over a linear accelerator is that because the same accelerating gap is used many times, it is both more space efficient and more cost efficient; particles can be brought to higher energies in less space, and with less equipment. The compactness of the cyclotron reduces other costs as well, such as foundations, radiation shielding, and the enclosing building. Cyclotrons have a single electrical driver, which saves both equipment and power costs. Furthermore, cyclotrons are able to produce a continuous beam of particles at the target, so the average power passed from a particle beam into a target is relatively high compared to the pulsed beam of a synchrotron.

However, as discussed above, a constant frequency acceleration method is only possible when the accelerated particles are approximately obeying Newton's laws of motion. If the particles become fast enough that relativistic effects become important, the beam becomes out of phase with the oscillating electric field, and cannot receive any additional acceleration. The classical cyclotron (constant field and frequency) is therefore only capable of accelerating particles up to a few percent of the speed of light. Synchro-, isochronous, and other types of cyclotrons can overcome this limitation, with the tradeoff of increased complexity and cost.

An additional limitation of cyclotrons is due to space charge effects – the mutual repulsion of the particles in the beam. As the amount of particles (beam current) in a cyclotron beam is increased, the effects of electrostatic repulsion grow stronger until they disrupt the orbits of neighboring particles. This puts a functional limit on the beam intensity, or the number of particles which can be accelerated at one time, as distinct from their energy.

Related technologies
The spiraling of electrons in a cylindrical vacuum chamber within a transverse magnetic field is also employed in the magnetron, a device for producing high frequency radio waves (microwaves). In the magnetron, electrons are bent into a circular path by a magnetic field, and their motion is used to excite resonant cavities, producing electromagnetic radiation.

A betatron uses the change in the magnetic field to accelerate electrons in a circular path. While static magnetic fields cannot provide acceleration, as the force always acts perpendicularly to the direction of particle motion, changing fields can be used to induce an electromotive force in the same manner as in a transformer. The betatron was developed in 1940, although the idea had been proposed substantially earlier.

A synchrotron is another type of particle accelerator that uses magnets to bend particles into a circular trajectory. Unlike in a cyclotron, the particle path in a synchrotron has a fixed radius. Particles in a synchrotron pass accelerating stations at increasing frequency as they get faster. To compensate for this frequency increase, both the frequency of the applied accelerating electric field and the magnetic field must be increased in tandem, leading to the "synchro" portion of the name.

In fiction
The United States Department of War famously asked for dailies of the Superman comic strip to be pulled in April 1945 for having Superman bombarded with the radiation from a cyclotron.

In the 1984 film Ghostbusters, a miniature cyclotron forms part of the proton pack used for catching ghosts.

Current facilities

 * The 88-Inch Cyclotron at Lawrence Berkeley National Laboratory
 * PSI Proton Accelerator – the highest beam current cyclotron in the world.
 * The Superconducting Ring Cyclotron at the RIKEN Nishina Center for Accelerator Based Science – the highest energy cyclotron in the world
 * Rutgers Cyclotron – Students at Rutgers University built a 12 in 1 MeV cyclotron as an undergraduate project, which is now used for a senior-level undergraduate and a graduate lab course.
 * TRIUMF – the largest single-magnet cyclotron in the world.

Historic cyclotrons

 * Ernest Lawrence's Cyclotron A history of cyclotron development at the Berkeley Radiation Laboratory, now Lawrence Berkeley National Laboratory
 * National Superconducting Cyclotron Laboratory of the Michigan State University – Home of coupled K500 and K1200 superconducting cyclotrons; the K500, the first superconducting cyclotron, and the K1200, formerly the most powerful in the world.

title: Cyclotron


text:
Talk:Graphics file format summary/Archive 1

The article stated (of GIF):
 * Deprecated for non-animated images in favor of PNG.

You can't just say that GIF is deprecated without saying who by. --Zundark, 2002 Mar 16

Also, "deprecated" implies that it was a standard in the first place; GIF has never been a standard of any kind. It was a proprietary format of CompuServe, Inc., and became something of a de facto standard for BBS and Web use, but no standards body ever endorsed it. --LDC


text:
Talk:Almost all

Untitled
I wonder if we should distinguish between "almost everywhere" and "almost all". I don't think "almost all" is used in measure theory at all, nor is "almost everywhere" used in number theory. Also, sometimes "almost all" means "all but finitely many". AxelBoldt

 * Yes, I think they should be separated. I've seen "almost all" used in a measure-theoretic sense, but it's not the usual usage. --Zundark, 2002 Mar 16

 * The real problem is that both "almost all" and "almost everywhere" are used in all of these contexts. Each of these is a special case of the most general situation (to my knowledge) where such terms are used -- the case where one has an ideal in a power set (or other Boolean algebra). Another example, used in Baire category theory, is meagre sets in a topological space. So these eventually need to be combined, but in conjunction with a rewriting of the article that describes the general case -- and yet gives precedence to the situations where one is most likely to see the phrases (such as measure theory). I'll have to do this someday, but we're probably OK for now. -- Toby 20:09 Feb 12, 2003 (UTC)

Is the 'perverse' statement correct?
The statement

'Perversely, if we allow "almost all" to mean "all but a countable set", then it follows that almost all prime numbers are even, since the set of all prime numbers is itself countable.'

looks debatable. It relies on the assumption that the countable set referred to in 'all but a countable set' is the set of all odd prime numbers. If the countable set referred to in 'all but ...' were the set of even primes, the statement 'almost all prime numbers are odd' holds. Conversely, if one chooses the set of odd primes, the statement 'almost all primes are even' holds. The conclusions I would draw from that are i) The statement is not sound as written and ii) defining 'almost all' as 'all but a countable set' depends on some ancillary statement about _which_ countable set is excluded. This could be fixed by extending the statement somewhat to include the issue above - but only if I'm more or less right about it... SLR Ellison (talk) 12:23, 21 June 2017 (UTC)

 * "a", in "all but a countable set", means "some", "any"; or more wordy, "there exists some countable set so that ...". Because of this existential quantification, it is not possible to have the truth of the statement "depend on ... _which_ countable set is excluded". Still, explaining that there is a quite implicit existential quantification in "all but a countable set" would help many people reading this to understand what's going on.
 * Also, I would heartily suggest to replace the word "perversely" (which does not transport any meaning except the emotion some writer had here) with "unfortunately" (which implies that this is a possible source of misunderstandings). --User:Haraldmmueller 18:49, 29 July 2017 (UTC)

"could mean" -> "can mean"?
Could "could mean" be replaced with "can mean" everywhere (except in the introduction)? "Could mean" sounds like "but there are strings attached to what I'm going to tell you, and I won't tell you about them - hehe" - which is mean for a dictionary. "Can mean" means "sometimes it actually means what I'm telling you - no strings attached". --User:Haraldmmueller 06:48, 31 May 2018 (UTC)
 * sorry for that, and for not noticing your request earlier. I'm just used to write that way. Is there anything else in the article that bothers you? Please ping me when you reply, this page is on my watchlist but I (almost) never check it. Professor Proof (talk) 18:49, 10 June 2018 (UTC)

“The Cantor set is also null”
Should this be “The Cantor set is almost null”?

Not a mathematician, but it seems wrong as written (since article is about “is almost”, and based on looking at Cantor set, which seems to not be null). 24.217.225.229 (talk) 09:12, 25 May 2023 (UTC)
 * The Cantor set is in fact a null set, i.e., it is a Lebesgue measurable set, and its Lebesgue measure is zero. ("The Cantor set is null" is math jargon for "the Cantor set is a null set", not for "the Cantor set is the empty set". I think this could be better phrased in the article.) -- Tea2min (talk) 06:11, 26 May 2023 (UTC)

title: Talk:Almost all