# Questions tagged [notation]

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

174 questions
Filter by
Sorted by
Tagged with
47 views

### What does x sign mean in functions

I came across this cross sign when reading a book. Does anyone know what does this mean in the context of a function?
439 views

### What is the meaning of this symbol that looks like an inverted uppercase A?

I found this symbol in a book I'm reading. Does anyone know what this symbol means? Does it mean for all js?
55 views

### What is the origin of the Bottom Type notation? Why does it look like... a bottom?

I couldn't help but notice the opening summary in Wikipedia's article on Bottom Types: In type theory, a theory within mathematical logic, the bottom type is the type that has no values. It is also ...
34 views

### How to write a job shop problem with these constraints in alpha|beta|gamma notation?

I have a job shop scheduling problem with the following characteristics. How would I write that in alpha|beta|gamma notation (see 1,2)? I know some of the parts, but not all. I add my suggestions in <...
26 views

### What does n with an index 0 mean in defenition of Theta/Big Omega/ Big-oh notation?

We define theta notation as follows: $\Theta(g(n))$ = {f(n): there are exist $c_1, c_2$ > 0 and $n_0$ such that 0 $\leq$ $c_1$g(n) $\leq$ f(n) $\leq$ $c_2$g(n) for all n > $n_0$}. I found an ...
13 views

### Set notation for ACL matrix

This might not be a computer science specific question and apologies if that is the case but it does come from material related to working out access control lists and I cannot understand the notation ...
30 views

### On lambda calculus notation: FGa

If we've got this expression: FGa where F and G are functions (as well as a, of course; but let's treat a as a constant). It must be understood that: first apply F taking G as input; then apply the ...
41 views

### Why are binary numbers sometimes written with one or more leading zeros that don't change the number (quantity) represented?

Binary numbers like '0110', or '00100101' are seen very often in all contexts. What are the leading (left hand side) zeroes for? Why did the writer not write '110' and '100101', respectively?
31 views

### Raising to the T in machine learning

What does it mean when in a machine learning paper there is $(arg)^{T}$, what does the T does to an arg in this 3b1b video on neural networks he puts the: $(w^{l-1})^{T}$
40 views

### Maximum Subarray Problem - Analyzing best case, worst case, and average case time complexity big o

New to the board, if this is the wrong section I apologize and I will delete it. Will be helpful to be provided correct exchange to guide me through this process of learning. If you have a given an ...
2k 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 ...
24 views

### Notations for dealing with generators in algorithms

This question is about generators, which are functions that return an item from a (usually very large or infinite) set on demand, an example from Python is: ...
34 views

### Infix to reverse polish notation (RPN)

I have an example: m = n = p = (-1) ^ (m + n + p) * (m + n + p); I don't know what to do with multiple "=". Should I treat them as a sign with the lowest priority or just put them in end of ...
73 views

### Cheat sheet for notation

I'm reading a paper which has quite a few formulas. I'm getting quite confused with some of the notation. For example I am able to pick-up on the BNF Notation (::= -> "is defined as") ...
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" ...
88 views

### Meaning of $\log^{O(1)}(a+b)$

What's the meaning of $\log^{O(1)}(a+b)$ ? Is it simply $(\log_2(a+b))^k$ where k is calculated in constant time ? That is the base 2 logarithm usually in computer science when no other base is set, ...
29 views

### Function notation/mapping for this type of functions?

In short, what is the proper function notation/mapping for this type of functions? From Wikipedia regarding maps: In the communities surrounding programming languages that treat functions as first-...
28 views

55 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, ...
100 views

### Determining asymptotic notation of a complex function

$$5n^4\log{n} - \frac{100n^2}{\log_4(n^2)} + 40$$ I am currently studying algorithm analysis and i need to express this function in terms of big O, theta and omega, so I should find C, and N0 for ...
35 views

89 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 ...
944 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 ...
38 views

### Asymptotic notation and random variables

I have two random variables $X$ and $Y$ and I want to bound the value of one in terms of the other (for now, I don't care about the actual distribution of their values). Suppose that the two ...
1k views

### Meaning of L* if L is a language

I can't find anywhere the meaning of $L^*$, given that $L$ is a language. I know $^*$ means repetition, for example $0^*$ = $\{ \epsilon, 0, 00, 000, \dots \}$. Or if $A$ is an alphabet $A^*$ are all ...
64 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 ...
31 views

### How the language $\{a^nb^mc^nd^m | n \geq1, \ m\geq1\}$ is used to check whether formal and actual parameters are equal?
How does the language $L=\{a^nb^mc^nd^m \mid n \geq1, m\geq1\}$ abstract the problem of checking that the number of formal parameters in the declaration of a procedure agrees with the number of actual ...
### How to denote a graph class which allows only $k$ instances of a certain induced subgraph?
Suppose that a graph class $\mathcal{C}$ is defined as follows: A graph $G$ belongs to $\mathcal{C}$ if, and only if $G$ is chordal, but has at most $k$ $5$-cycles. I am aware that the ...