Skip to main content
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 ...
Vincenzo's user avatar
  • 3,397
54 votes
Accepted

What is the name the class of functions described by O(n log n)?

It's called linearithmic time, and is a special case of a more general class known as quasi linear. As the name may suggests, the algorithms that fall in this class almost run in linear time; in fact ...
Roukah's user avatar
  • 771
45 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, ...
Foo Bar's user avatar
  • 536
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 ...
leftaroundabout's 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 ...
D.W.'s user avatar
  • 162k
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 ...
Draconis's user avatar
  • 7,168
17 votes

What is the name the class of functions described by O(n log n)?

linearithmic: adj. Of an algorithm, having running time that is O(N log N). Coined as a portmanteau of ‘linear’ and ‘logarithmic’ in Algorithms In C by Robert Sedgewick (Addison-Wesley 1990, ISBN ...
miracle173's user avatar
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 ...
Discrete lizard's user avatar
  • 8,303
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$.
D.W.'s user avatar
  • 162k
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 ...
David Richerby's user avatar
13 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 ...
Jouni Sirén's 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 ...
David Richerby's 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 ...
Andrej Bauer's user avatar
  • 30.9k
12 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. ...
Jörg W Mittag's user avatar
11 votes

What is the name the class of functions described by O(n log n)?

I've always heard O(n log n) described as "log-linear" which seems about right to me.
Dylan Skola's 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 ...
John L.'s user avatar
  • 39k
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 ...
Mario Cervera's user avatar
9 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 ...
Hendrik Jan's user avatar
  • 30.7k
9 votes
Accepted

Is Big-Theta a more accurate description of worst case run time than Big-O?

Yes. Your understanding is correct on all points!
D.W.'s user avatar
  • 162k
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 ...
David Richerby's 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....
Derek Elkins left SE's 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....
Nathaniel's user avatar
  • 15.9k
8 votes

Is Big-Theta a more accurate description of worst case run time than Big-O?

O(f(n)) is also used when there is no simple function that your runtime is close to. For example: Find the smallest prime factor of n by trial division, finishing when a factor is found: There are O(n^...
gnasher729's user avatar
  • 31.1k
7 votes

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

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 ...
trunklop's user avatar
  • 171
7 votes

What is the name the class of functions described by O(n log n)?

This was too long for a comment, so I wrote an answer. I did not add this to my first answer because a lot of people already upvoted my first vanswer and I am not sure they agree with this answer, too....
miracle173's user avatar
7 votes
Accepted

What does the $O^*$ notation mean?

Similarly as $O$ notation which "ignores constant factor", $O^*$ notation "ignores polynomial factor" that is: $f(n) = O^*(g(n))$ if there exists some polynomial $p$ such that $f(n) \leq p(n) g(n)$ ...
holf's user avatar
  • 956
7 votes
Accepted

Meaning of the notation Typ := TVar | (Typ → Typ)

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 $...
D.W.'s user avatar
  • 162k
7 votes

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

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 ...
usul's user avatar
  • 4,139
7 votes
Accepted

Weight functions in graph algorithms

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 ...
John L.'s user avatar
  • 39k
7 votes
Accepted

Definition feels contradictory (Computational Complexity Theory)

$\mathbb{N}$ can be defined as the set of non-negative integers 0, 1, 2, ... You should check the definition in the book you're reading. However, there is no contradiction regardless of how $\mathbb{N}...
John Kemeny's user avatar
  • 16.7k

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