# Questions tagged [notation]

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

154 questions
Filter by
Sorted by
Tagged with
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)$ ...
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 ...
3k 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 ...
14k 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 ...
1k 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 "...
7k 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 ...
1k 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,...
1k views

111 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 ...
490 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 ...
864 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,...
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 ...
46 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, ...
60 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 ...
104 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 ...
2k 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 ...
51 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 ...
69 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 ...
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 ... 1answer 210 views ### For complexity classes A and B, what does$A^B$mean? What does$A^B$mean where A and B are complexity classes? The "Polynomial Hierarchy" page says:$A^B$is the set of decision problems solvable by a Turing machine in class A augmented by an oracle ... 1answer 44 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,... 1answer 53 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 ... 1answer 243 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 ... 1answer 213 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 ... 2answers 117 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\...
I am studying Quantum Computing using the book Quantum Computation and Quantum Information of Michael Nielsen and Isaac Chuang. I am confused by the meaning of the $\oplus$ (addition modulo 2) symbol ...