Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [notation]

Use this tag whenever you have a question about what some particular symbol/notation means.

47
votes
2answers
7k views

Order of growth definition from Reynolds & Tymann

I am reading a book called Principles of Computer Science (2008), by Carl Reynolds and Paul Tymann (published by Schaum's Outlines). The second chapter introduces algorithms with an example of a ...
45
votes
10answers
11k views

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

I totally understand what big $O$ notation means. My issue is when we say $T(n)=O(f(n))$ , where $T(n)$ is running time of an algorithm on input of size $n$. I understand semantics of it. But $T(n)$ ...
18
votes
2answers
2k views

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

In the paper "A Conflict-Free Replicated JSON Datatype", I encountered this notation for formally defining "rules": What is this notation called? How do I read it? For example: the ...
16
votes
3answers
9k views

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

In my Algorithms and Data Structures course, professors, slides and the book (Introduction to Algorithms, 3rd edition) have been using the word NIL to denote for ...
15
votes
2answers
590 views

What is the origin of λ for empty string?

I usually use the symbol $\varepsilon$ for empty string (empty word or null string). But I know some people use $\lambda$ instead of $\varepsilon$. I think $\varepsilon$ is derived from the word "...
9
votes
1answer
879 views

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

I'm learning vantage point trees, and I met this while reading the paper Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces by Peter Yianilos (Proceedings of SODA 1993,...
9
votes
1answer
5k views

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

Let us say for instance I am doing string processing that requires some analysis of two strings. I have no given information about what their lengths might end up being, so they come from two distinct ...
8
votes
2answers
1k views

Double exponentials vs single exponentials

Here are four tenets I cannot reconcile: Double exponential time algorithms run in $O(2^{2^{n^k}})$ time with $k \in \mathbb{N}$ constant Exponential time algorithms run in $O(2^{n^k})$ with $k \in \...
6
votes
4answers
165 views

Can I use ellipses in first order logic

I ask, because I have to come up with a first-order logic sentence that shows that there are exactly N objects in the universe. What I've been able to come up with is: $$ \forall x \; \exists y_1, ...
6
votes
1answer
655 views

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

I want to denote the class of problems solvable by linear space multi-tape Turing machines. I have seem in many places this class being denoted by $SPACE(n)$. But why is the notation $SPACE(O(n))$ not ...
6
votes
1answer
390 views

type theory notation troubles

I'm working through "Types and Programming Languages" by Benjamin Pierce and I don't quite understand the notation. Particularly on Page 106, (chapter 9 Simply Typed Lambda-Calculus) there is a lemma (...
6
votes
1answer
124 views

Use of Big O Notation in a recent paper by Khot et al

I'm reading a paper about Constraint Satisfaction Problems, specifically "A Characterization of Strong Approximation Resistance", Subhash Khot, Madhur Tulsiani, Pratik Worah (ECCC TR13-075). The ...
6
votes
0answers
91 views

Where did our present regex notation originate?

First question, and my apologies if it is off-topic! This question suggests to me I may not be totally off-base. Where did our present regex notation originate? I am particularly wondering how <...
5
votes
2answers
2k views

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

I thought the order of precedence of operators and quantifiers was arbitrary, but I don't really understand why those three have the same "strength" in relation to other operators (e.g., ¬ will have ...
5
votes
1answer
708 views

What does ⊢ mean in operational semantics?

I have been reading a couple of texts on operational semantics. In [1], the evaluation of expressions is done as in this rule: $\frac{<e_1,s>\;\Rightarrow \;n_1\;\;\;<e_2,s>\;\Rightarrow ...
5
votes
3answers
255 views

Help understand the notation

I'm reading a computer science paper, this one: https://arxiv.org/abs/1608.03960. It uses certain notation in one of the illustrations (Figure 9, page 8 in the PDF version) that I don't understand how ...
5
votes
1answer
103 views

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

We can denote by $X\to X$ the set of all functions from $X$ to $X$. Therefore, we can use the following statement to say that $f$ is a function from $X$ to $X$: $$f\in X\to X$$ But we usually state ...
5
votes
1answer
164 views

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

I read an example that said explain what "$f(n)$ is $n^{O(1)}$" means. I can't interpret the $n^{O(1)}$ syntax. I know what Big $O$ notation is, its just that this example looks odd to me.
5
votes
1answer
77 views

In type systems, is there a name for SQL's way of cutting and combining record types into new types?

I'd like to have this feature in my application programming language (which these days, is Scala), but when I went to learn more about it on the internets, I realized I don't know the name of it. I'm ...
5
votes
2answers
145 views

Numeral systems other than unary used in nature or in animal and human behaviours

Representing numeric values using positional notation is one of the milestones in the history of arithmetic. Babylons used a base 60 system, Maya a base 20 system; base 10 system became "the standard" ...
5
votes
1answer
158 views

When it is said an algorithm runs in exponential time, is it meant it has complexity $O(2^n)$, or $2^{O(n)}$?

Also, are they equivalent or are they different? Examples of algorithms/Turing Machines that run in complexity of one but not the other would be much appreciated.
4
votes
3answers
143 views

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

In the paper "introduction to type theory" by Herman Geuvers, it states the following definition for the type theory of propositional logic (I've added "convention 2" just for reference): Given ...
4
votes
2answers
973 views

Understanding the Reasoning Behind These Typing Rules

So the expression $\Gamma \ \vdash \ e:\sigma$ states that under assumptions $\Gamma$, the expression $e$ has type $\sigma$. Then we have the following rules: \begin{array}{cl}\displaystyle {\frac {x:...
4
votes
1answer
108 views

What is the origin of using Q to denote a set of states in an automaton?

When talking about DFAs and NFAs as 5-tuples, it's common to use the letter $Q$ to denote the set of states in the automaton and to denote individual states with names like $q_0$, $q_1$, etc. Is ...
4
votes
1answer
747 views

Determining Number of States in a Turing Machine

I am looking at an example Turing machine in my textbook, Automata and Computability by Dexter C. Kozen, and I'm confused as to how they determine the number of states this particular machine has. The ...
4
votes
1answer
21 views

In ISGCI, unit interval graphs are denoted as ($C_{n+4}$,$S_3$,claw,net)-free. Is this an accurate notation?

When I search unit interval graphs in ISGCI, it says that the unit interval graphs (UIG) are equivalent to ($C_{n+4}$,$S_3$,claw,net)-free graphs. I am confused about the definition of an $S_3$ graph....
4
votes
1answer
360 views

Finding the language of a context-free grammar?

Given following question: Let $G$ be a context-free grammar, $G=(V, \Sigma, R, S)$, that has start variable $S$, set of variables $V = \{S\}$, set of terminals $\Sigma = \{0, 1\}$, and set of rules $...
4
votes
1answer
65 views

Programming Symbols : Instance/Instantiation

Is there a generally accepted symbol for indicating instantiation. That is indicating an object is an instance of a class. My first guess is to use a left arrow with a double or triple line but this ...
3
votes
5answers
7k views

What is the difference between $\log^2(n)$, $\log(n)^2$, $(\log n)^2$, $\log (n^2)$ and $\log \log n$?

In research articles (e.g. this one's abstract), I often see the complexity of an algorithm expressed using a somewhat ambiguous notation: $\log^2(n) = ?$ $\log(n)^2 = ?$ $(\log n)^2 = (\log(n)) \...
3
votes
2answers
151 views

What does the $O^*$ notation mean?

I'm recently reading some papers on the maximum independent set problem, all the algorithms' time complexity is donated by $O^*()$ notation, like $O^*(1.0836^n)$. One paper says "the $O^*$notation ...
3
votes
2answers
83 views

Origins of misconception about using equality signs with Landau notation

From "Misconception 1" from Søren S. Pedersen's blog, and as many have seen before, a major misconception in Big-O (and others) notation is to say a function is "equal" to Big-O of some other function:...
3
votes
1answer
79 views

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

What does $\leq_{\mathrm{P}}$ mean? Is it supposed to mean less than or equal polynomial time?
3
votes
2answers
845 views

What type of formal notation is being used here to represent functional algorithms?

Interested in learning more about algorithm design in functional programming, I picked up Andrew Bird's Pearls of Functional Algorithm Design. I have experience with a number of programming languages,...
3
votes
2answers
76 views

Meaning of , and ; in relation to defining context

I have seen use of , and somewhere use of ; when defining context : $$\dfrac{\phi \ , \ \Gamma \ \vdash } {} $$ somewhere else i have seen : $$\dfrac{\phi \ ; \ \Gamma \ \vdash ...
3
votes
2answers
268 views

Expressing that a function converges to 1 with linear rate using Landau notation

I am working on an algorithm which approximates a certain optimal quantity. The approximation becomes better when the size of the problem ($n$) becomes larger: the difference from the optimum is ...
3
votes
1answer
60 views

What does $\mathbf{Q}^+$ mean in approximation texts?

Often, in a lot of texts concerning approximation algorithms I see the following notation (for example, here in page 19 of the PDF or the first page of the introduction): ... and a cost function on ...
3
votes
2answers
45 views

Notation for a Kleene fixed point with a starting element

Assume a CPO $Q,\leq$ and a Scott-continuous function $f : Q \rightarrow Q$. As it is known, the chain $\bot \leq f(\bot) \leq \ldots \leq f^n(\bot)$ (where $f^n$ denotes the function $n-1$-times ...
3
votes
2answers
101 views

Differences in Postfix Syntax

A question about postfix/RPN came up in my class due to the current ACSL competition. Is it a rule or convention that 4 + (5 * 6) in infix is written 4 5 6 * + in postfix, as opposed to 5 6 * 4 + in ...
3
votes
1answer
59 views

What does does $O$ mean in this context?

I understand big O notation in computational complexity theory, but I don't see how it applies in the equation below. From Pattern Recognition and Machine Learning: If we weren't familiar with the ...
3
votes
1answer
105 views

Hierarchy of complexity classes $\bigcup_{c > 0} \mathrm{Time}(2^{c \log^k n})$, w.r.t. $k$

This is a true/false question: For each integer $k > 1$, define the complexity class $\sf QP_k := \bigcup_{c > 0} Time(2^{c \log^k n})$. Then for all integers $k > 1$, $\sf QP_k \subsetneq ...
3
votes
1answer
59 views

What do the commas separating atomic events in a Relational Calculus formula means?

For instance, take the example of this book here on page 30. About the formula $$ Q(x,x') = R(x), S(x,y), S(x',y), R(x') $$ described there, what do the commas mean? Is it the same as an "and" ...
3
votes
2answers
47 views

Help on the notation of the 2-bit operation: $\frac 12{(I+Z_1Z_0)}$

This was adapted from Quantum Mechanichs for Computer Scientists. On this equation, we have $I$ representing the identity operator, with $Z$ being defined for 1 bit as: $$ Z|0⟩ = |0⟩, \quad Z|1⟩ = -|...
3
votes
1answer
43 views

Formal notations of equivalencence between floating point expressions

In an informal context, most programmers might call these two expressions "equal" and no one would be mislead: (a + b) + c a + (b + c) For floating point numbers,...
3
votes
1answer
49 views

How to state that a complexity bound does not depend on a given parameter size?

I am often ill at ease with Landau (Big O) notation, because it seems often to be abusing mathematical notation. The best example is the use of the equal sign to express a set membership. And this can ...
3
votes
1answer
216 views

Notation for average case complexity of an algorithm

I'm just wondering what the correct notation is when referring to an average case complexity of an algorithm that was calculated by doing empirical analysis. For example, I have tested my algorithm ...
3
votes
2answers
30 views

Can I notate time complexity depending on the result of an algorithm?

I have a program that calculates the first year some two events happen on the same day. I have not calculated any upper limit for the year. The time complexity of the program would be equivalent to O(...
3
votes
1answer
181 views

Properties of Reverse Polish Notation expressions that are algebraically invariant

The RPN expressions a b + c * and f d e + * are algebraically equivalent, though the names of the variables are different ...
3
votes
2answers
108 views

Combining these two results into one asymptotic notation

Assume you have two parameters, $N \gg 1$ and $\epsilon < 1$. I have an algorithm (and matching lower bounds) that runs in $\Theta(\epsilon^{-1}+\log N)$ for $\epsilon > N^{-1}$, and $\Theta\...
3
votes
0answers
197 views

Why mantissa and exponent are stored differently in a float?

As we know, in IEEE 754 standard, float number's exponent and mantissa are stored differently. While the exponent is stored as an unsigned number, taking advantage of the bias, the mantissa is in sign-...
3
votes
0answers
129 views

Correct mapping “update” notation for computer science papers

A nice easy one. I'm interested to know the most standard and accepted way to denote the update of a mapping in the context of a theoretical computer science paper. By example, suppose we have a ...