107

Strictly speaking, $O(f(n))$ is a set of functions. So the value of $O(f(n))$ is simply the set of all functions that grow asymptotically not faster than $f(n)$. The notation $T(n) = O(f(n))$ is just a conventional way to write that $T(n) \in O(f(n))$. Note that this also clarifies some caveats of the $O$ notation. For example, we write that $(1/2) n^2 + ...


77

The paragraph is wrong. Unfortunately, it looks exactly like the kind of thing that a student who does not understand the material would write as an answer to an exercise. This sort of nonsense has no place in a textbook. Make no sudden movements. Put the book down. Step away from the book. We say that the "order of growth" of the sequential search ...


43

$O$ is a function $$\begin{align} O : (\mathbb{N}\to \mathbb{R}) &\to \mathbf{P}(\mathbb{N}\to \mathbb{R}) \\ f &\mapsto O(f) \end{align}$$ i.e. it accepts a function $f$ and yields a set of functions that share the asymptotic bound of (at most) $f$. And strictly speaking the correct notation is thus $$ (n \mapsto T(n)) \in O(n\mapsto f(n)) $$ ...


26

This is a standard notation for an inference rule. The premises are put above a horizontal line, and the conclusion is put below the line. Thus, it ends up looking like a "fraction", but with one or more logical propositions above the line and a single proposition below the line. If you see a label (e.g., "LET" or "VAR" in your example) next to it, that's ...


25

The issue comes down to ambiguous terminology. $(a^b)^c = a^{bc}$, but $a^{(b^c)} \neq a^{bc}$. In other words, exponents aren't associative. Conventionally, nested exponentials without parentheses are grouped in this second way, because it's more useful. So $2^{2^n} = 2^{(2^n)} \neq 2^{2n}$. If we wanted to talk about $(2^2)^n$, we could just write $2^{2n}...


24

As far as I'm concerned, null, nil, none and nothing are common names for the same concept: a value which represents the “absence of a value”, and which is present in many different types (called nullable types). This value is typically used where a value is normally present, but may be omitted, for example an optional parameter. Different programming ...


17

Order of precedence is simply a notional convenience. There is no notion of strength here, just notation. All three operators are unary operators with notation "$\circ\ \cdot$", where $\circ$ denotes the operator symbol $\exists, \forall,\neg$ and $\cdot$ the operand. There can never be any ambiguity in which order to apply these operators: the operator to ...


16

$a^{(b^c)}$ is not the same as $(a^b)^c$. When people write $2^{2^k}$, they usually mean $2^{(2^k)}$, not $(2^2)^k$.


15

This is something that I think is not explicitly pointed out or not pointed out with enough emphasis in many, even introductory, CS/type theory/logic texts. $\vdash$ doesn't mean anything. Instead, in this example, the three place relation $- \vdash - \Rightarrow -$ is what has meaning. Except that was a lie. It doesn't a priori have meaning either. That ...


14

The algorithms in the paper you link to are described in a notation quite similar to Pascal, a language that treats pointers in a very particular way. In Pascal, pointers are declared as references to values of specific types (a pointer to an integer can never refer to a boolean, for instance). The upward arrow, in the example you reproduce, is a ...


14

It depends on what definitions you use. Sipser [1] defines $\mathrm{SPACE}(f(n))$ to be the class of languages decided by Turing machines using $O(f(n))$ cells on their work tapes for inputs of length $n$. Papadimitriou [2], on the other hand defines it to be the class of languages decided by Turing machines using at most $f(n)$ cells on the ...


13

Yes, of course. This is fine and perfectly acceptable. It is common and standard to see algorithms whose running time depends upon two parameters. For instance, you will often see the running time of depth-first search expressed as $O(n+m)$, where $n$ is the number of vertices and $m$ is the number of edges in the graph. This is perfectly valid. The ...


13

Formally speaking, $O(f(n))$ is a the set of functions $g$ such that $g(n)\leq k\,f(n)$ for some constant $k$ and all large enough $n$. Thus, the most pedantically accurate way of writing it would be $T(n)\in O(f(n))$. However, using $=$ instead of $\in$ is completely standard, and $T(n)=O(f(n))$ just means $T(n)\in O(f(n))$. This is essentially ...


11

Prologue: The big $O$ notation is a classic example of the power and ambiguity of some notations as part of language loved by human mind. No matter how much confusion it have caused, it remains the choice of notation to convey the ideas that we can easily identify and agree to efficiently. I totally understand what big $O$ notation means. My issue is when ...


10

Strictly speaking, your statement is invalid because $\ldots$ is not part of the syntax of first-order logic. However, your statement is an abbreviation of a statement in first-order logic. For example, when $n = 3$, your statement is an abbreviation of the bona fide statement $$ \forall x, \exists y_1, y_2 (x \neq y_1) \land (x \neq y_2). $$ As long as you ...


10

The German Wikipedia claims that $\lambda$ comes from "leer", which means "empty" in German. That seems plausible, as German used to be one of the major languages in mathematics. Chomsky used $I$ as the empty string (or actually as the identity element for string concatenation) in his early papers. Some people in combinatorics still use $1$ as the empty ...


10

In The Algorithm Design Manual [1], you can find a paragraph about this issue: The Big Oh notation [including $O$, $\Omega$ and $\Theta$] provides for a rough notion of equality when comparing functions. It is somewhat jarring to see an expression like $n^2 = O(n^3)$, but its meaning can always be resolved by going back to the definitions in terms of ...


8

Probably the notation originates from the "Finnish school". My copy of 'Formal Languages' by Arto Salomaa (Academic Press, ACM monograph series, 1973) uses $\lambda$ for the empty string. And so does his 1969 book 'Theory of Automata' (Pergamon Press). We move back. The classic 'Finite Automata and Their Decision Problems' by M.O. Rabin and D.Scott (April ...


8

It's short-hand for "$n^{f(n)}$ for some function $f(n)\in O(1)$". In other words, the function is at most $n^c$ for some constant $c$. You can see this by directly substituting the definition of $O(1)$ in the expression. $g(n)=n^{O(1)}$ if there's constant $c$ such that, for all large enough $n$, $f(n)\leq n^{c\cdot 1} = n^c$. This ...


8

No, they're mostly notational variations. There are different connotations to the different notations, and different notations are common in different fields where they can mean quite different things. Also, sometimes they are used in a particular context for different (but usually related) things. You'll, of course, have to see how it has been defined in ...


7

There is no such thing as the "format" for algorithms. A general agreement¹ is to use pseudocode, i.e. code that abstracts from the particulars of specific programming languages, machines and/or libraries. The most important thing is to be consistent. If you want to follow a specific style, I recommend you pick up some textbooks on algorithms and/or data ...


7

$O$ is not only used in simple statements like $f(n)=O(g(n))$. It is also used to give error terms as in $f(n) = 14\, n\log n + O(n)$. The interpretation is still the same as @usul has described in his answer: There is a function $h \in O(n)$ so that $f(n) = 14\, n\log n + h(n)$. Here, writing $f(n) \in 14\, n\log n + O(n)$ would emphasize the fact that ...


7

It should have been defined wherever you've seen it used. It normally stands for polynomial-time reducibility of one kind or another; usually many-one reducibility.


7

Here is a very informal explanation that might help people unfamiliar with formal notations to get a foot in the door. It does not replace a formal definition! The Ap is the state of your system or your running program. "State" can mean a lot of things but in this case it seems to include a list of all defined local variables and their values. Why is Ap a ...


7

Intuitively, a type variable is like a variable in an expression, except that it stands in for a type rather than standing in for a number/bitstring/etc. Formally, we choose a countably infinite set $\mathsf{TVar}$, and then define a type variable to be a member of $\mathsf{TVar}$. The notation $\mathsf{Typ}:=\mathsf{TVar}|(\mathsf{Typ}\to \mathsf{Typ})$ ...


7

Usually, statements like $$f = O(g)$$ can be interpreted as $$ \text{there exists } h \in O(g) \text{ such that }f = h\,. $$ This becomes more useful in contexts like David Richerby mentions, where we write $f(n) = n^3 + O(n^2)$ to mean "there exists $g(n) \in O(n^2)$ such that $f(n) = n^2 + g(n)$." I find this existential quantifier interpretation so ...


7

Here is the original statement in CLRS. Assume that we have a connected, undirected graph $G$ with a weight function $w: E\to\Bbb R$, and we wish to find a minimum spanning tree for $G$. It is pretty good to understand "a weight function $w:E\rightarrow \mathbb{R}$" as "an edge has a weight". In fact, that is how I would interpret that notation in a rush ...


6

$X \vdash Y$ means "The information in $X$ lets you prove that $Y$ is true." This is true in logic in general, as well as in type theory specifically. I often read this as "$X$ says that $Y$ is true." So, If $\Gamma\vdash t\colon T$ and $x\notin\mathrm{dom}(\Gamma)$, then $\Gamma,x\colon S\vdash t\colon T$ translates as If we can prove that that $t$ ...


6

This set is a formal way of expressing a "checking set." What this is asking is, "Is $y$ a valid output for $w$, where the space of all valid input/output pairs is the binary relation $R$?" Let $\Sigma_i$ be the alphabet of the input and $\Sigma_o$ be the alphabet of outputs. The checking relation, $R\subseteq\Sigma_i^* \times \Sigma_o^*$ is the binary ...


6

What does > denote here? It's not stated explicitly, but a reasonable meaning can be inferred from context. The authors assume that the data can be sorted so there has to be some (total) order relation $\leq$ (canonically) on the elements. We don't care what the elements are, so we do not fix the relation, either. In any given situation, we would know what ...


Only top voted, non community-wiki answers of a minimum length are eligible