Skip to main content

Questions tagged [notation]

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

Filter by
Sorted by
Tagged with
48 votes
10 answers
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)$ ...
doubleE's user avatar
  • 591
47 votes
2 answers
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 ...
JW.'s user avatar
  • 581
41 votes
4 answers
11k views

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

In "Big O", common notations have common names (instead of saying, "Oh of some constant factor"): O(1) is "Constant" O(log n) is "Logarithmic" O(n) is "Linear" O(n^2) is "Quadratic" O(n * log n) ...
GlenPeterson's user avatar
26 votes
3 answers
6k views

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

I would like to know if there is any reason why many programming languages use the notation % for the modulo operator? It is used in the most "famous" ...
zdm's user avatar
  • 1,046
22 votes
3 answers
24k 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 ...
user avatar
20 votes
1 answer
15k 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 ...
corsiKa's user avatar
  • 423
19 votes
2 answers
5k 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 ...
natevw's user avatar
  • 293
17 votes
2 answers
3k 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 "...
nekketsuuu's user avatar
14 votes
5 answers
52k 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)) \...
Suzanne Soy's user avatar
11 votes
3 answers
3k views

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

Question I was asked: Does it make a difference if I say "The worst case run time is $O(n^2)$ vs the worst case run time is $\Theta(n^2)$?" To me, the only difference is that when we say $O(...
Carter Falkenberg's user avatar
9 votes
1 answer
2k 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,...
QhelDIV's user avatar
  • 93
8 votes
2 answers
2k 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 \...
badroit's user avatar
  • 727
8 votes
4 answers
5k views

Arrow notation?

can someone explain what the following notation is? For j <- 1 to n Legal <- True I've seen these in various places, including wikipedia articles. It ...
Daniel's user avatar
  • 190
7 votes
3 answers
429 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 ...
Haspemulator's user avatar
7 votes
1 answer
792 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 (...
Hath995's user avatar
  • 215
6 votes
4 answers
281 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, ...
Colin's user avatar
  • 63
6 votes
1 answer
679 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 ...
Springberg's user avatar
6 votes
2 answers
17k views

Operator precedence in propositional logic

there is some kind of priorities for the elements in propositional logic ? for example : p ∧¬q → r , given this ,we there may be two options (p ∧¬q) → r OR p ∧ (¬q → r) , which one is the correct ?...
Roberto Fernandez Diaz's user avatar
6 votes
1 answer
676 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.
rert588's user avatar
  • 261
6 votes
1 answer
623 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 ...
templatetypedef's user avatar
6 votes
1 answer
148 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 ...
Mark's user avatar
  • 215
6 votes
0 answers
110 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 <...
cxw's user avatar
  • 161
5 votes
2 answers
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 ...
Phil's user avatar
  • 53
5 votes
1 answer
1k 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 ...
josh's user avatar
  • 341
5 votes
2 answers
1k 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:...
Lance's user avatar
  • 2,243
5 votes
1 answer
137 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 ...
user56834's user avatar
  • 3,982
5 votes
1 answer
4k views

What does the R superscript notation mean in regular/formal languages?

What does the capital R superscript notation mean in regular languages? I am working on a homework assignment and don't recall my professor mentioning what the what the R superscript means. For ...
Unnamed's user avatar
  • 153
5 votes
1 answer
105 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 ...
Rob N's user avatar
  • 153
5 votes
2 answers
178 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" ...
Vor's user avatar
  • 12.6k
5 votes
1 answer
123 views

Exact meaning of $2^{\mathcal{O}(f(n))}$

In Sipser's Introduction to the Theory of Computation he uses the notation $2^{\mathcal{O}(f(n))}$ to denote some asymptotic running time. For example he says that the running time of a single-tape ...
Daniel's user avatar
  • 163
4 votes
3 answers
430 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 ...
user56834's user avatar
  • 3,982
4 votes
2 answers
442 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 ...
Mengfan Ma's user avatar
4 votes
2 answers
109 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:...
Ryan Dougherty's user avatar
4 votes
2 answers
3k views

Why are Complexity Notations Called Asymptotic?

Why do we use the term "asymptotic" in complexity. Although I know what an asymptote is, but what is an asymptote doing here?
aditya lath's user avatar
4 votes
1 answer
2k 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 ...
tdark's user avatar
  • 155
4 votes
1 answer
185 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.
Kalernor's user avatar
4 votes
2 answers
145 views

What does $o_n(1)$ mean?

I'm trying to read the following article, and in the abstract they write: Let $\xi$ be a non-constant real-valued random variable with finite support, and let $M_n(\xi)$ denote a $n\times n$ random ...
L. breitman's user avatar
4 votes
1 answer
94 views

Difference between ⫾ (U+2AFE) and ⫿ (U+2AFF) in the context of Dijkstra's Guarded Command Language?

Continuing https://tex.stackexchange.com/questions/435986/how-to-draw-the-box-of-dijkstras-guarded-command-language, what is the difference in the intended usage of ⫾ (Dijkstra choice, U+2AFE) and ⫿ (...
user avatar
4 votes
1 answer
40 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....
padawan's user avatar
  • 1,445
4 votes
1 answer
958 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 $...
m0meni's user avatar
  • 143
4 votes
1 answer
173 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 ...
Carel's user avatar
  • 143
3 votes
2 answers
2k views

Weight functions in graph algorithms

In text books, for instance in the 3rd edition of Introduction to Algorithms, Cormen, on page 625, the weights of the edge set $E$ is defined with a weight function $w:E\rightarrow \mathbb{R}$. Why ...
RichArt's user avatar
  • 133
3 votes
2 answers
939 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,...
David Kaczynski's user avatar
3 votes
1 answer
20k views

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

I feel like I'm confusing myself perhaps but I'm having a bit of trouble figuring out how exactly this language works. I'm given the following regular expression (a + b)* (abba* + (ab)*ba) Can ...
trungnt's user avatar
  • 173
3 votes
1 answer
784 views

What does > mean in this TAOCP solution?

For our assignment we have to implement a solution given to one of the problems in The Art of Computer Programming by D.E. Knuth (Ex24; Chapter 5: Sorting; TAOCP, Vol3, 2nd). However, I fail to ...
Shaffaf Ahmed's user avatar
3 votes
2 answers
271 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 ...
Erel Segal-Halevi's user avatar
3 votes
1 answer
54 views

graph theory single bar vs double bar size notation

A follow-up on https://stackoverflow.com/questions/15037679/what-do-the-absolute-value-bars-mean-in-graph-theory What is the difference between single bar $|G|$ and double bar $||G||$ notation (both ...
J. Schmidt's user avatar
3 votes
2 answers
64 views

Parentheses after Typing Environment

I've been reading about System F Omega lately, and I keep stumbling across a construct in typing rules that I cannot find an explanation of: Γ(x) = k. For example, ...
Andrew Thaddeus Martin's user avatar
3 votes
3 answers
76 views

Why is subarray $A[p..k-1]$ empty when $k=p$?

I'm working through a proof of correctness for merge sort. I'm given a loop invariant for a for loop, which makes reference to a subarray $A[p..k-1]$. During the initialization step of the ...
Data's user avatar
  • 215
3 votes
2 answers
120 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 ...
Adam-Morgan's user avatar