# Questions tagged [notation]

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

143 questions
Filter by
Sorted by
Tagged with
66 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 ...
256 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 ...
192 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 ...
29 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 ...
61 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 ...
56 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 ...
22 views

40 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. ...
132 views

### What does $|w|$ mean in the statement “ $|w|$ where $w \in L \subset \Sigma^*$”?

In my assignment I find these symbols: $|w|$ where $w \in L \subset \Sigma^*$ I believe it means the lexikografic value of a word, but I am not 100% certain. Let me phrase my question this way: ...
45 views

### How to represent a map data structure mathematically

Wondering how to represent a map object such as the following mathematically: var foo = { a: 10, b: 'bar', c: true } You could say that it was a function ...
27 views

### Notation for field access in Algorithm

While writing array index in an algorithm $a[i]\gets v$ is conventionally used. Is the notation $a_{i}\gets v$ also used ? If the algorithm uses struct or ...
41 views

Which notation can be used for expressing how many times that function or subroutine called during a run of a program? Example program pseudocode: $a \gets 0 \\ \textbf{While } a \neq 5 \textbf{ do}... 1answer 60 views ### what is the 'x :=' part mean in a hoare triple? In Hoare logic, there's a thing called a Hoare triple, e.g.$$\begin{array}{ccccc} \{x = 2\} & & x := x+1 & & \{x = 3\} \end{array}.$$ What does '$x :=$' mean? 2answers 166 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 ... 3answers 10k 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 ... 1answer 161 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. 3answers 265 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 ... 1answer 75 views ### Is this a standard representation of a 'space' character? I recently came across a handwritten note with directions to push a string of text into a database. There was a strange character in the string I've never seen before, a lower case 'b' with a forward ... 1answer 39 views ### 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 } } \...
Let $G = (V, E)$ be a digraph, and consider the set $\left\{ v \in V \; \middle| \; \left(\{v\} \times V \right) \cap E \neq \varnothing \right\}$, the set of vertices which form edges with other ...
### 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.