108 votes
Accepted

O(·) is not a function, so how can a function be equal to it?

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 ...
user avatar
  • 3,172
78 votes
Accepted

Order of growth definition from Reynolds & Tymann

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 ...
user avatar
46 votes
Accepted

Is there any reason why the modulo operator is denoted as %?

The earliest known use of % for modulo was in B, which was the progenitor of C, which was the ancestor (or at least godparent) of most languages that do the same, ...
user avatar
  • 546
44 votes

O(·) is not a function, so how can a function be equal to it?

$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 ...
user avatar
29 votes
Accepted

What is the purpose of using NIL for representing null nodes?

As far as I'm concerned, null, nil, none and nothing are ...
user avatar
25 votes
Accepted

What is this fraction-like "discrete mathematics"–style notation used for formal rules?

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 ...
user avatar
  • 143k
25 votes
Accepted

Double exponentials vs single exponentials

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 ...
user avatar
  • 6,940
19 votes
Accepted

Can a Big-Oh time complexity contain more than one variable?

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 ...
user avatar
  • 143k
17 votes

Why do ¬, ∀ and ∃ have the same precedence?

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 ...
user avatar
  • 6,998
16 votes

Double exponentials vs single exponentials

$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$.
user avatar
  • 143k
15 votes

What does ⊢ mean in operational semantics?

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, ...
user avatar
14 votes
Accepted

What does up arrow ($\uparrow$) mean in pseudocode?

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 ...
user avatar
14 votes
Accepted

Notation: SPACE(n) vs SPACE(O(n))

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 ...
user avatar
13 votes

O(·) is not a function, so how can a function be equal to it?

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 ...
user avatar
13 votes

Is there any reason why the modulo operator is denoted as %?

This is very likely a historical development. Looking at this table, we see that C was likely the first language to use % for modulo. Its predecesor BCPL used ...
user avatar
  • 28.3k
11 votes

What is the origin of λ for empty string?

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 ...
user avatar
11 votes

O(·) is not a function, so how can a function be equal to it?

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 ...
user avatar
  • 34.7k
11 votes
Accepted

Arrow notation?

In general, there are no standards for pseudo-code. Everybody can design their own pseudo-code however they want to. Normally, an author should define the conventions they use for their pseudo-code. ...
user avatar
10 votes
Accepted

Can I use ellipses in first order logic

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 ...
user avatar
10 votes

O(·) is not a function, so how can a function be equal to it?

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 ...
user avatar
8 votes
Accepted

Origins of misconception about using equality signs with Landau notation

$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 ...
user avatar
  • 6,519
8 votes

What is the origin of λ for empty string?

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 ...
user avatar
  • 27.7k
8 votes
Accepted

What does $n^{O(1)}$ mean?

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 ...
user avatar
8 votes
Accepted

Is there a formal difference between $f:X \to X$ and $f\in X \to X$?

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....
user avatar
8 votes

Arrow notation?

Left arrows often mean assignment or modification. This pseudo-code can be interpreted as "For j from 1 to n, the variable Legal is given the value True" Check this page: https://en....
user avatar
  • 7,193
7 votes
Accepted

type theory notation troubles

$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." ...
user avatar
7 votes

What is a conventional format for presenting algorithms?

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 ...
user avatar
  • 71k
7 votes

Why are Complexity Notations Called Asymptotic?

I would like to quote from "Concrete Mathematics" (Chapter 9) by Ronald Graham, Donald Knuth, and Oren Patashnik. It does mention curves and asymptotes. The word asymptotic stems from a ...
user avatar
  • 9,219
7 votes
Accepted

What's the difference between the concatenation and union of symbols within a language

Simply put, the kleene star of concatenation gives $$(ab)^* = \{\epsilon, ab, abab, ababab, ...\} $$ while the kleene star of union gives $$(a+b)^* =\{\epsilon,a,b,aa,ab,ba,bb,\ldots\}$$ so you got ...
user avatar
  • 20.4k
7 votes

What does the $\leq_{\mathrm{P}}$ symbol mean?

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.
user avatar

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