107

Strictly speaking, $O(f(n))$ is a set of functions. So the value of $O(f(n))$ is simply the set of all functions that grow asymptotically not faster than $f(n)$. The notation $T(n) = O(f(n))$ is just a conventional way to write that $T(n) \in O(f(n))$. Note that this also clarifies some caveats of the $O$ notation. For example, we write that $(1/2) n^2 + ...


43

$O$ is a function $$\begin{align} O : (\mathbb{N}\to \mathbb{R}) &\to \mathbf{P}(\mathbb{N}\to \mathbb{R}) \\ f &\mapsto O(f) \end{align}$$ i.e. it accepts a function $f$ and yields a set of functions that share the asymptotic bound of (at most) $f$. And strictly speaking the correct notation is thus $$ (n \mapsto T(n)) \in O(n\mapsto f(n)) $$ ...


17

Order of precedence is simply a notional convenience. There is no notion of strength here, just notation. All three operators are unary operators with notation "$\circ\ \cdot$", where $\circ$ denotes the operator symbol $\exists, \forall,\neg$ and $\cdot$ the operand. There can never be any ambiguity in which order to apply these operators: the operator to ...


13

Formally speaking, $O(f(n))$ is a the set of functions $g$ such that $g(n)\leq k\,f(n)$ for some constant $k$ and all large enough $n$. Thus, the most pedantically accurate way of writing it would be $T(n)\in O(f(n))$. However, using $=$ instead of $\in$ is completely standard, and $T(n)=O(f(n))$ just means $T(n)\in O(f(n))$. This is essentially ...


11

Prologue: The big $O$ notation is a classic example of the power and ambiguity of some notations as part of language loved by human mind. No matter how much confusion it have caused, it remains the choice of notation to convey the ideas that we can easily identify and agree to efficiently. I totally understand what big $O$ notation means. My issue is when ...


10

In The Algorithm Design Manual [1], you can find a paragraph about this issue: The Big Oh notation [including $O$, $\Omega$ and $\Theta$] provides for a rough notion of equality when comparing functions. It is somewhat jarring to see an expression like $n^2 = O(n^3)$, but its meaning can always be resolved by going back to the definitions in terms of ...


7

Usually, statements like $$f = O(g)$$ can be interpreted as $$ \text{there exists } h \in O(g) \text{ such that }f = h\,. $$ This becomes more useful in contexts like David Richerby mentions, where we write $f(n) = n^3 + O(n^2)$ to mean "there exists $g(n) \in O(n^2)$ such that $f(n) = n^2 + g(n)$." I find this existential quantifier interpretation so ...


7

Here is the original statement in CLRS. Assume that we have a connected, undirected graph $G$ with a weight function $w: E\to\Bbb R$, and we wish to find a minimum spanning tree for $G$. It is pretty good to understand "a weight function $w:E\rightarrow \mathbb{R}$" as "an edge has a weight". In fact, that is how I would interpret that notation in a rush ...


5

It means that each edge has only one weight, which is defined as a real number. So, this definition in compact form excludes many cases, for example: an edge doesn't have weight at all an edge has two (or more) weights an edge has weight as a complex number etc.


3

Non-deterministic guarded choice is an associative-commutative binary operator. My guess is that the character ⫾ U+2AFE is intended to be used as an infix binary operator and the character ⫿ U+2AFF, which is larger and described as “n-ary”, is intended to be used as a prefix operator which is typeset larger, in prefix position, and typically with a subscript ...


3

I don't know if there is a correct or recommended usage of Unicode codepoints for the LTL operators, but the mapping we used in LaTeX was the following: □ (U+25A1) => \Box ◇ (U+25C7) => \Diamond ○ (U+25CB) => \medcirc (from txfonts/pxfonts)


3

The class $O(f(n))$ consists of all functions $\phi$ such that for some $N,c > 0$, we have $\phi(n) \leq Cf(n)$ for all $n \geq N$. The class $2^{O(f(n))}$ is simply $$ 2^{O(f(n))} = \{ 2^{\phi(n)} : \phi(n) = O(f(n)) \}, $$ which is essentially what you wrote. A different way of looking at this is that $O(f(n))$ stands for some function $\phi(n)$ such ...


3

I thought the order of precedence of operators and quantifiers was arbitrary Certainly the rules of precedence could be set up in different ways, but some ways are more helpful and convenient than others, and there are principled reasons for this. but I don't really understand why those three have the same "strength" in relation to other operators (e.g., ...


3

You seem to have misunderstood pretty much every part of the statement $$\sum_{i,j\in\{1,2,3\},i\neq j} x_{ij}=3>2=|\{1,2,3\}|-1\,.$$ I get that $x_{ij}$ is equal to 3, No, the sum of all values $x_{ij}$ where $i$ and $j$ are distinct values from $\{1,2,3\}$ is equal to $3$. but why the "> 2" ? Because three is bigger than two. And ...


2

The point of these constraints is eliminating subtours, which the source explains quite clearly. So for every subset $S$ of the nodes, such as $\{1,2,3\}$, they add a constraint which says $\Sigma_{i,j \in S, i \neq j} x_{ij} \leq |S| - 1$. So when this constraint is satisfied, there is no way to form a cycle on the vertices in $S$. Now, if this constraint ...


2

The language $$L=\{a^nb^mc^nd^m \mid n \geq1, m\geq1\}$$ abstracts agreement of parameter and argument count for the case where there are exactly two procedures, one with $n$ parameters, declared with $a^n$ and used with $c^n$, and the other one with $m$ parameters, declared with $b^m$ and used with $d^m$. Each procedure is called exactly once and the ...


2

Just to underline the point which has been made several times, allow me to quote from N. G. de Bruijn, Asymptotic Methods in Analysis: The common interpretation of all these formulas can be expressed as follows. Any expression involving the $O$-symbol is to be considered as a class of functions. If the range $0 < x < \infty$ is considered, then $O(1)...


2

Many other posters have explained that the Big-O can be thought of as denoting a set of functions, and that the notation $n^2 = O(n^3)$ indicates that $n^2$ (as a function of $n$) is in the set denoted by $O(n^3)$ (again considering $n$ as the parameter). In English text, you may prefer to write "$n^2$ is in $O(n^3)$" to avoid confusion. Although the ...


2

The vertices of $G'$ are exactly given by $(v, i)$ with $v\in Nodes$ and $i \in \{0, 1,\cdots, k\}$. Edges in $G'$ are between $(u, i)$ and $(v, i)$ if $(u, v)$ is an edge of $G$, or between $(u, i)$ and $(v, i + 1)$ if $(u, v)$ is an edge of $G$ and $v\in S_{i+1}.$ We know $Nodes$ are 6 nodes, i.e., $H, B1, B2, Bus, P, M$ and $k=3$ as there are three ...


2

For bounded sets, the usual convention is to use interval notation. Specifically, $[a,b]$ means "real numbers between $a$ and $b$, inclusive", while $[a\mathinner{\ldotp \ldotp}b]$ means "integers between $a$ and $b$, inclusive". Changing any of the square brackets to curved means that endpoint is not included: $a \not\in (a,b]$, for example. In this case, ...


2

It's a convention. One reason for the convention is that the length of an array $A[i..j]$ is $j-i+1$, so if $j=i-1$, we should get an array of length zero. Due to this reason, we sometime consider $A[i..j]$ to be undefined when $j < i-1$; in other cases, the issue does not arise, and $A[i..j]$ is just the empty array whenever $j < i$. In yet other ...


2

Given a language $L$, let $L_0 = \{\epsilon\}$ and, for $i\geq 1$, let $L_i = \{w_1\circ \dots\circ w_i \mid w_j\in L \text{ for each } j\}$, where $\circ$ denotes concatenation. Then the Kleene closure of $L$ is the language $L^* = \bigcup_{i\geq 0} L_i$.


1

A[i..j] is a convention. We could define it any way we like, but we define it in a way that gives useful results. One property is that if we reduce the right index by 1, then we lose the rightmost element. For example, going from A[5..10] to A[5..9] we lose element 10. So what is A[i..i] and what would you expect going from A[i..i] to A[i..i-1]?


1

Yes, you may consider this as axiom. Or try to make a definition that still works for a > b case - most probably it will give you an empty array in this case. For example, "all elements with indexes i >= a and i < b".


1

Perhaps what you're missing (although you seem to suspect) is that the left hand side of the $⊢$ is not just for specifying what types variables have. In fact, as you've noted, it doesn't necessarily have all (or only) the variables on the right hand side (although in this situation it does only have variables, not things like $λy.x : α→β$). What it's doing ...


1

The notation $A \le_pB$ means problem $A$ can be reduced to problem $B$ in polynomial time, and that $B$ is at least as hard as $A$, because solving $B$ means solving $A$. $A \le_pB$ $\equiv$ $B \ge_pA$ It does $\mathbf{not}$, however, mean $B \le_pA$, and to claim as much you would have to show the appropriate reduction.


1

$\Bbb N$ denotes the set of natural numbers, that is, the set $\{0,1,2, \cdots\}$. If $\Bbb N$ is the set of positive integers, the treatment will be roughly the same. So in $1$ they build a class of the empty word $\lambda$ and $z = B$ has to be the language by her self to be in the language? Since the above paragraph in the question, $z=z(C)$ is ...


1

Per Dmitri's hint on it being called de-amortisation, here's some applicable references on the subject: Rao Kosaraju S., Pop M. (1998) De-amortization of Algorithms. In: Hsu WL., Kao MY. (eds) Computing and Combinatorics. COCOON 1998. Lecture Notes in Computer Science, vol 1449. Springer, Berlin, Heidelberg Abstract: De-amortization aims to convert ...


1

The case, when the operation performs the worst, is commonly called the worst case. The common name for the optimization you mentioned is de-amortization. To denote the fact that operations take $O(1)$ on average, you may say that the time complexity of a single operation is amortized $O(1)$. As far as I know, amortized complexity analysis was first ...


1

Yes, as confirmed by Gokul, $\max(p,q)$ just means the larger one of its two parameters, $p$ and $q$. It can also apply to more parameters such as $\max(p, q, r, s, t)$, where it means the largest of all 5 variables or values. Its opposite is $\min$, which is used in the same way but means the smaller one of two values or the smallest one of all given ...


Only top voted, non community-wiki answers of a minimum length are eligible