# 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
17 views

75 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 ...
355 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 ...
32 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 ...
267 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 ...
58 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 ...
26 views

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. ...
54 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 ...
42 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 64 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 198 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 ... 1answer 84 views ### Does big-Oh notation in optimization follow the same convention as in CS? I first learned big-Oh (little-Oh, big-Theta.....) complexity for growth of functions using CLRS in a computer science class. Now I am doing a project on optimization. In our optimization class, we ... 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. 1answer 83 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 151 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: ... 3answers 274 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 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.