# Tag Info

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 ...
• 3,397
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 ...
• 771
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, ...
• 536

### 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 ...
• 1,681
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 ...
• 162k
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 ...
• 7,168

### 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 ...
• 542

### 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 ...
• 8,303

### 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$.
• 162k
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 ...

### 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 ...
• 472

### 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 ...

### 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 ...
• 30.9k
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. ...
• 6,270

### 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.
• 121

### 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 ...
• 39k

### 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 ...
• 3,734

### 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 ...
• 30.7k
Accepted

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

Yes. Your understanding is correct on all points!
• 162k
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 ...
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....
• 12.1k

### 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....
• 15.9k

### 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^...
• 31.1k

### 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 ...
• 171

### 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....
• 542
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)$ ...
• 956