# Questions tagged [notation]

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

148 questions
Filter by
Sorted by
Tagged with
122 views

### On asymptotic complexity class notation?

Is the class of problems with complexity $O(n^{n^\epsilon})$ at every $\epsilon>0$ same as class of problems with complexity $O(n^{f(n)})$ at every $f(n)\in\omega(1)$ and hence both classes are ...
392 views

### How to read 'max min' and 'min max'?

Here is an exercise I came across while studying MaxFlow / MinCut and I'm rather stumped: Designate $G = (V, E)$ as an undirected graph that has at least two vertices. Every edge $(e)$ on this ...
173 views

### What is the Haskell-style type signature called (i.e., who is it named after)?

A type signature in Haskell is written in the following format: functionName :: arg1Type -> arg2Type -> returnType There's a (hyphenated, after a person or ...
60 views

### How to express taking the next bit of an infinite string in small-step semantics?

I have to write a rule as part of a small step operational semantics (https://en.wikipedia.org/wiki/Operational_semantics). Whenever this rule is applied, the next bit belonging to an infinite bit ...
21 views

### How to understand the mathematical constraint of potentials?

Good evening! I am studying scheduling problems and I have some difficulties understanding constraints of potentials: Let be $t_j$ the time when a task $j$ starts, and $t_i$ the time when a task $i$ ...
46 views

32 views

32 views

### Did Menezes et al. switch the letters $\mu$ and $\lambda$ in Floyd's cycle detection note 3.8?

The letters $\mu$ and $\lambda$ are usually used to represent, respectively, the length of the tail of the graph and length of the cycle in the graph. But Menezes on note 3.8, page 91 (or PDF-page 6),...
12 views

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

### Banker's algorithm

I have a question regarding the banker's algorithm step 2. When it says the Need[i] <= work. Need is an n * m matrix and work is a vector of length m. I want to know what Need[i] <= Work means. ...
37 views

### Representing Graham Scan Mathematically

I am aware the convex hull algorithm known as Graham Scan can be computed by sorting the derived vectors from points given in a 2D plane. One then iterates through a series of Cross Product ...
88 views

### What does an = sign with an x beneath it mean?

I am studying for a test in Logic right now, and saw the symbol $\underset{x}{=}$, which is used like this: $I \underset{x}{=} I'$. I've seen it in the solutions of questions like this one: Prove ...
21 views

### Selection type generated by nested loops where initial value is current value of parent loop

Consider the generator of the selections: ...
37 views

### What are these notations O(1)/O(n)/O(log n)? [duplicate]

I am a newbie here I recently read tutorials on java about collection framework. The time complexity of various objects in reading/writing data What does it mean? ...
77 views

### Notation: $L_R = \{w\#y\space|\space R(w,y)\}$?

What is the set $$L_R = \{w\#y\space|\space R(w,y)\}$$ Specifically what kind of conditional is $R(w,y)$? Also what's the purpose of $\#$? This comes from page 2 of the Clay paper on P vs NP: http://...
63 views

### Clarification notation in CLRS runtime analysis

I am learning algorithms from the clrs book. I am having trouble understanding the notation the book has placed. The book wrote the following: $t_j$ denote the number of times the ...
46 views

### Meaning of <==> in documentation? [closed]

Title says it all. I just need to confirm that... X.__add__(y) <==> x+y ...doesn't mean anything more than just 'same as' The problem is Google returns zero ...
### Why $\left\lceil lgn \right\rceil <lgn+1\le 2lgn\quad for\quad all\quad n\ge 2$
I have some confusion about 3.2-4 in CLRS. Here is the question : Is the function $\left\lceil \log { n } \right\rceil !$ polynomially bounded? Is the function \$\left\lceil \log { \log { n } } \...