# Question
Title: Why Is My Proof Of Asymptomatic Time Complexity Of A Dynamic Array Using The Accounting Method Getting A Wrong Answer?
I had trouble formatting the summation symbols, so if anyone knows how to do it correctly feel free to edit.

I just read the asymptomatic analysis chapter from CLRS. While the aggregation and potential method are clear to me, I thought I should do some extra practice with the accounting method. My goal was to prove that if you have an array size 1, and when it fills up, you double the size, results in a time complexity of O(1) per operation. Using aggregate analysis, here is the proof I came up with:

If you call append n times, then the time complexity would be this:

$\sum\_{i=1}^{\log n} \frac{1}{2^i}$

which is less than

$\sum\_{i=1}^{+\infty} \frac{1}{2^i}$

which is equal to $2n$. So, the time complexity for all N operations will be O(N), so the time complexity for a single operation is O(1).

However, if the size starts at 1, then adds by 1 instead of multiplying by 2 (meaning, size starts 1, then becomes 2, then becomes 3, etc...) then the time complexity should be O(N), which I get using aggregate analysis. $\sum\_{i=1}^{n} (i+1)$

the extra 1 comes from actually placing the next element. This is equal to around (n(n + 2)) / 2, or O(N ^ 2) for all N operations, and O(N) for a single operation, which is correct. However, using the accounting method I get another answer. The actual cost of placing an element is 1, and the asymptomatic cost I set is 2. So the first time costs 2, and the second call the copying doesn't take any extra time because I prepaid it before, and the extra cost of placing that element is 2. So, it becomes:

$\sum\_{i=1}^{n} 2$

which is equal to O(N) for all total operations, and O(1) for a single operation. This isn't the correct output. Where did I go wrong, and how can I fix it?

# Answer
First of all notice that your first aggregate analysis should read $\sum\_{i=1}^{\log n} 2^i = 2^{\log n + 1} - 2 \< 2n$. (What you have written makes no sense since $\sum\_{i=1}^\infty \frac{1}{2^i} \le 1$, which would mean that the aggregate complexity is upper bounded by a constant regardless of the number of operations).

Then in your last analysis you can't just place one extra credit on each element because it would only pay for **the first time** that such element is copied (i.e., only for the next insertion).
> 1 votes

---
Tags: time-complexity, asymptotics, runtime-analysis
---


# Question
Title: Variant of greedy algorithm for vertex cover
Does the following approximation algorithm for vertex cover also have an approximation ratio of 2? Why? Why not?

Input: $G = (V,E)$

1. Set $C \gets \emptyset$ and $E' \gets E$.
2. **while** $E' \neq \emptyset$ **do**:
    * Pick any edge $(u,v) \in E'$.
    * $C \gets C \cup \\{u\\}$.
    * Remove from $E'$ all edges incident to $u$.
3. **return** $C$.

# Answer
No, this is a terrible algorithm. Consider a star graph: the vertices are $x,y\_1,\ldots,y\_n$, and the edges are $(x,y\_1),\ldots,(x,y\_n)$. Your algorithm goes over the edges in an arbitrary order, and always picks the $y$ vertices. It ends up with $n$ vertices rather than the optimal $1$ vertex solution.
> 1 votes

---
Tags: algorithms, algorithm-analysis, approximation, vertex-cover
---


# Question
Title: Solving subgraph isomorphism in polynomial time
So I am a bit confused about the reduction between SAT, subgraph isomorphism (SI) and graph isomorphism (GI). I know that GI is in NP, and that SI is NP-complete. So I'm thinking if we can decide instances of SAT in polynomial time, then we can also solve GI and SI in polynomial time since SAT is NP-complete and if one NP-complete problem is solved, then all others are also solved.

Am I correct? Thank you!

# Answer
Here is a more general theorem:

> Let $X$ be some NP-complete problem. Then $X$ can be solved in polynomial time iff all problems in NP can be solved in polynomial time.

Indeed, if all problems in NP can be solved in polynomial time, then since $X$ is in NP, then $X$ can be solved in polynomial time.

In the other direction, suppose that $X$ can be solved in polynomial time. Let $Y$ be any problem in NP. Since $X$ is NP-hard, there is a polytime reduction $f$ from $Y$ to $X$. Using this reduction, we can reduce $Y$ to $X$, and so solve $Y$ in polynomial time. (I'm only sketching this part, since this is a standard argument which I assume you were shown in class.)
> 1 votes

---
Tags: np-complete, reductions, polynomial-time-reductions
---


title: Radix sort slower than Quick sort?

text:
# Question
Title: Radix sort slower than Quick sort?
I would like to demonstrate that sometime radix-sort is better than quick-sort. In this example I am using the program below:

```
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <time.h>
#include <math.h>

int cmpfunc (const void * a, const void * b) {
   return ( *(int*)a - *(int*)b );
}

void bin_radix_sort(int *a, const long long size, int digits) {
    assert(digits % 2 == 0);

    long long count[2];
    int *b = malloc(size * sizeof(int));
    int exp = 0;

    while(digits--) {
        // Count elements
        count[0] = count[1] = 0;
        for (int i = 0; i < size; i++)
            count[(a[i] >> exp) & 0x01]++;

        // Cumulative sum
        count[1] += count[0];

        // Build output array
        for (int i = size - 1; i >= 0; i--)
            b[--count[(a[i] >> exp) & 0x01]] = a[i];

        exp++;
        int *p = a; a = b; b = p;
    };

    free(b);
}

struct timespec start;

void tic() {
    timespec_get(&start, TIME_UTC);
}

double toc() {
    struct timespec stop;
    timespec_get(&stop, TIME_UTC);
    return stop.tv_sec - start.tv_sec + (
        stop.tv_nsec - start.tv_nsec
    ) * 1e-9;
}

int main(void)
{
    const long long n = 1024 * 1024 * 50;
    printf("Init memory (%lld MB)...\n", n / 1024 / 1024 * sizeof(int));

    int *data = calloc(n, sizeof(int));

    printf("Sorting n = %lld data elements...\n", n);

    long long O;
    tic();
    O = n * log(n);
    qsort(data, n, sizeof(data[0]), cmpfunc);
    printf("%lld %lf s\n", O, toc());

    int d = 6;
    tic();
    O = d * (n + 2);
    bin_radix_sort(data, n, d);
    printf("%lld %lf s\n", O, toc());
}

```

It performs as follow:

```
$ gcc bench.c -lm
$ ./a.out
Init memory (200 MB)...
Sorting n = 52428800 data elements...
931920169 1.858300 s
314572812 1.541998 s

```

I know that Quick Sort will perform in **O(n log n)** while Radix Sort will be in **O(d (n + r))** ~= **O(6 * n)**. For `n = 52428800`, `log(n) = 17`. I am then expecting Radix Sort to be 3 times faster than Quick Sort...

This is not what I observe.

What am I missing?

# Answer
> 3 votes
1. qsort is not Quicksort. qsort is whatever the implementor of the standard library decided.
2. Sorting 50 million identical values is highly unrepresentative. There are qsort implementations that will sort 50 million identical, or 50 million sorted or reverse sorted elements in linear time.
3. Radix sort of 50 million numbers with six digits is obviously nonsense. Six digits means you expect only 64 different values and therefore would use counting sort. With less than 26 digits it doesn't make sense.
4. Your radix sort does an awful lot of copying, and worse, uncached copying.
5. Your radix sort doesn't produce a correctly sorted result if digits is an odd number.
6. Your qsort call doesn't produce a correctly sorted result if the array contains very large and very small numbers.

---
Tags: complexity-theory, time-complexity, sorting, quicksort, radix-sort
---


# Question
Title: VC dimension of only the rim of a unit disk
Suppose we have an origin centered circle, ie $x^2 + y^2 =1$, so it's in $\mathbb{R}^2$ (2D). It will be classified as 1 if it lies only on this arc, and will be labeled 0 otherwise. What is the VC dimension?

I think the answer is 2. Any two points can be shattered $(++, -+, +-, --)$. But if we have three points $\\{(x\_1,y\_1),\dots,(x\_3,y\_3)\\}$ that all have the label 1, with radius $r\_1 = r\_2 = 1$, and $r\_3 = 0$, it is impossible to shatter them. Is my intuition correct?

Or can I construct the sample points to my liking (to get the maximum VC dim) so that only the positive labels will be on the rim (have some combination of $x\_i^2 + y\_i^2 = 1$), and have 0 labels to not lie on the rim, therefore have infinite VC dimension?

# Answer
> 1 votes
Let us prove the following general result:

> Let $\mathcal F$ be a class of functions from $\mathcal X$ to $\\{0,1\\}$. If $\mathcal F$ has VC dimension $d$ then $|\mathcal F| \geq 2^d$.

Indeed, if $\mathcal F$ has VC dimension $d$ then $\mathcal F$ shatters some set $S \subseteq \mathcal X$ of size $d$. This means that for any function $\phi\colon S \to \\{0,1\\}$ we can find a function $f\_\phi \in \mathcal{F}$ that agrees with $\phi$ on $S$. Note that if $\phi \neq \psi$ then $f\_\phi \neq f\_\psi$. Since there are $2^d$ different functions from $S$ to $\\{0,1\\}$, we conclude that $\mathcal F$ must contain at least $2^d$ functions. $\square$

In particular, the VC dimension of a class of functions containing a single function is zero.

---
Tags: machine-learning, vc-dimension
---


# Question
Title: Language of words whose run lengths are all distinct
Assume $ \Sigma=\\{0,1\\}$, is $L$ a regular language? If it is not, how should we prove it with pumping lemma?

> $$L = \\{1^{a\_1} 0^{a\_2}\ldots 01^{a\_k} \mid k \in \mathbb N , a\_i \geq 0 , \text{ the $a\_i$ are all different}\\} $$

# Answer
> 1 votes
The definition of your language is not completely clear, but whatever it is, if you consider $$ L \cap 1^\* 0^\* = \\{ 1^a 0^b \mid a \neq b \\} $$ then you immediately see that $L$ is not regular.

If you have to prove it using the pumping lemma, then simply take a proof that works for the above language; it will work for $L$ as well.

---
Tags: regular-languages, pumping-lemma
---


# Question
Title: Naming facts exported from blocks in Isabelle/HOL
I'm using Isabelle/HOL. Isabelle exports the last fact in a block, allowing the context that contains the block to use it. Ordinarily when I generate facts, I can give them convenient names. How do I name facts that are exported from blocks?

Simple example:

```
lemma mylemma: "i=i"
proof -
  {
      fix j::nat
      have "j=j" by auto
    }

    show ?thesis using ‹⋀j. j = j› by auto
  qed

```

Right now I use `‹⋀j. j = j›` to refer to the exported fact as a proposition literal. I'd like to be able give it a simple name, though, as when I named the lemma `mylemma`. Thanks for any suggestions!

# Answer
> 5 votes
From section 1.1.2 in the document isar-ref: you can reference facts via explicit name, implicit name and literal position. In this case, the explicit name has not been provided. I believe that the canonical method to provide an explicit name is to reference the fact of interest by its implicit name immediately after the end of the block. For example,

```
lemma mylemma: "i = i"
proof -
  {
    fix j :: nat
    have "j = j" by auto
  }
  note name = this
  show ?thesis using name by auto
qed

```

---

As a side remark, I would like to mention that general questions about Isabelle or the syntax of Isar are best posed on Stack Overflow. I believe that this would drastically increase the chances of your questions being answered promptly.

---
Tags: isabelle
---


title: Classes of circle rims

text:
# Question
Title: Classes of circle rims
The input space is a unit circle, $\mathcal{X} = \mathbb{S}^1 \subset \mathbb{R}^2$. There is class $\mathcal{F}$ of arcs on $\mathbb{S}^1$, where a point is labeled 1 if it is on the arc, and 0 otherwise. We want to find the VC dimension of $\mathcal{F}$

I think the answer is 2. Any two points can be shattered $(++, -+, +-, --)$. But if we have three points $\\{(x\_1,y\_1),\dots,(x\_3,y\_3)\\}$ that all have the label 1, with radius $r\_1 = r\_2 = 1$, and $r\_3 = 0$, it is impossible to shatter them. Is my intuition correct?

# Answer
> 0 votes
In fact, the VC dimension is 3.

To show this, we need to show that there is a set of 3 points which is shattered, and that no set of 4 points is shattered.

All sets of 3 points behave the same, but for definiteness let us choose three points $x,y,z$ which form the corners of an equilateral triangle. By symmetry, there are only 4 cases to consider:

* $\emptyset$: choose some arc which avoids all points.
* $\\{x,y,z\\}$: choose the complement arc.
* $\\{x\\}$: choose a small arc around $x$.
* $\\{y,z\\}$: choose the complement arc.

This shows that the VC dimension is at least 3.

To show that the VC dimension is at most 3, let us consider some arbitrary set of points $x,y,z,w$, presented in clockwise order starting at an arbitrary point. An arc that contains both $x$ and $z$ must contain either $y$ or $w$, and in particular there is no arc that contains exactly $\\{x,z\\}$.

---
Tags: machine-learning, vc-dimension
---


# Question
Title: House painting problem where the house row is split and converged back
I am trying to solve a house painting problem: There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x k cost matrix. For example, costs\[0\]\[0\] is the cost of painting house 0 with color 0; costs is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

This can be solved with dynamic programming (see solution in link house painting). I am trying to solve a very similar problem, but my house row is splitting somewhere in the middle and converging (but sometimes it doesn't), as shown in the picture attached:

Above you can see the problems that I am facing... Can I solve those problems with dynamic programming ? Is there any other solution for those problems ?

# Answer
The problem you described can be solved in polynomial time using dynamic programming whenever the topology of the input houses is a tree (a path is just an even easier special case).

Unless $P=NP$, the problem is not solvable in polynomial time when the input instance is a general graph, since the $k$-coloring problem can be easily reduced to your problem.

However, in your particular case you are in luck since your input instances can always be decomposed in any of the following ways:

* into $2$ paths by deleting two vertices.
* into $2$ trees by deleting one vertex.

You can then guess the the color(s) of the deleted house(s) and update the cost matrix of their neighbors so that if a house $u$ is adjacent to a deleted house $v$ and $v$ is colored with color $c$, the cost of coloring $u$ with $c$ will be $+\infty$ (effectively ensuring that no optimal solution will color $u$ with $c$).

If $k$ is the number of colors, $n$ is the number of houses, and you delete $2$ vertices, solving your problem will take time $O(k^2 \cdot n k) = O(n k^3)$.

If you delete a single house and solve the problem on the resulting tree, you can reduce the time complexity to $O(k \cdot nk) = O(n k^2)$.

---

To solve the problem on trees in time $O(n k)$, root the input tree $T$ in an arbitrary vertex $r$ and let $C(u,c)$ be the cost of coloring vertex $u$ with color $c = \\{1, \dots, k\\}$.

Define $OPT\[u,c\]$ as the minimum cost needed to color the subtree of $T$ rooted in $u$ with the additional constraint that vertex $u$ must have a color different from $c$.

Then, if $u$ is a leaf of $T$, you have $OPT\[u,c\] = \min\_{c' \in \\{1, \dots, k\\} \setminus c} C(u,c')$. Otherwise, if $u$ is an internal vertex of $T$, let $v\_1, \dots, v\_h$ be its children. You have $OPT\[u, c\] = \min\_{c' \in \\{1, \dots, k\\} \setminus c} \left( C(u, c') + \sum\_{i=1}^h OPT\[v\_i, c'\] \right)$.

The optimal solution is $\min\\{ OPT\[r, 1\], OPT\[r, 2\] \\}$ (since if $r$ is not colored with color $1$ in an optimal coloring then $OPT\[r, 1\]$ is exactly the minimum cost to color $T$, while if $r$ is colored with color $1$ then it is not colored with color $2$ and $OPT\[r, 2\]$ must be the minimum cost needed to color $T$).

A similar argument shows that, for each fixed vertex $u$, all supbroblems $OPT\[u, c\]$ can be solved in an overall time of $O(k)$ (there are only two interesting values of $c$). The time complexity follows.
> 1 votes

---
Tags: algorithms, graphs, dynamic-programming
---


# Question
Title: Sum weighted nodes between nodes in a DAG efficiently
Suppose we have a directed acyclic graph $G=(V,E)$, such that all vertices have a addible weight, e.g. there is a function $weight: V \to \mathbb{R} $. Moreover two vertices $v,w \in V$ are given and we write $G\_{v,w}$ for the subgraph of $G$ that consists of all vertices and path between $v$ and $w$, both included.

The task is to compute the sum of the weight $weight(u)$ of all vertices $u \in G\_{v,w}$. In addition if $v'$ and $w'$ are two vertices, with $G\_{v,w}\subset G\_{v',w'}$, then the computation on $G\_{v,w}$ should not be repeated (kind of divide and conquer, but on subgraphs) to compute the weight of $G\_{v',w'}$.

Is that possible?

# Answer
> 1 votes
A vertex $z$ is "between $v$ and $w$" in $G$ (that is there is a path in $G$ from $v$ to $w$ that traverses $z$) if and only if both the following conditions are true: 1) there is a path from $v$ to $z$ in $G$; and 2) there is a path from $w$ to $z$ in $\overline{G}$, where $\overline{G}$ is the graph obtained from $G$ by reversing its edges.

Using any standard visit algorithm you can compute the set $A$ of vertices reachable from $v$ in $G$ and the set $B$ of vertices reachable from $w$ in $\overline{G}$.

Then you can compute $C = A \cap B$ and find the desired quantity as $\sum\_{z \in C} \text{weight}(z)$. Each of the above steps can be performed in linear time.

---
Tags: algorithms, graphs, divide-and-conquer
---


# Question
Title: Are there graphs for which A* cannot be admissible?
Wikipedia states that "On infinite graphs with a finite branching factor and edge costs that are bounded away from zero $ (d(x,y)\>\varepsilon \>0$ for some fixed $\varepsilon$), A\* is guaranteed to terminate only if there exists a solution."

Does this mean that, if I have such a graph, then there is no admissible A\* which exists for this graph? When one says that A\* is not admissible, this means that its heuristic is not admissible, right?

Furthermore, is it correct to say that a heuristic is only admissible with respect to a graph - not generally admissible?

For example, if I have a infinite graph which has a finite branching factor, and the cost of each edge is half of the cost of the edge preceding it (something like this: $goal\leftarrow\_{\_{c=2}} start \rightarrow\_{\_{c=1}}q1 \rightarrow\_{\_{c=1/2}} q\_2 \rightarrow ...$), the heuristic and therefore the A\* is necessarily inadmissible as there exists no fixed $\epsilon\>0$ that is less than the cost of any edge?

To generalize, the $epsilon$ constraint is to make sure that there is no infinite path who's total cost converges, thereby assuring termination?

Any clarification is appreciated. Thanks!

# Answer
The heuristic function $h:V \longrightarrow \mathbb{R}\_{\geq 0}$ is \*an input to the $A^\*$ algorithm. If the function is *admissible* then $A^\*$ algorithm gives you the solution; however as you have noted for infinite graphs the edge weights must have a positive lower bound.

The point of the heuristic function is to find the shortest path in the *least amount of time*, *i.e.* lower the computational complexity; *because you are making informed decisions based on a heuristic* (hence the name).

Recall the heuristic function is ***admissible*** if $h(v)$ is always less than (or equal to) the true path cost to the goal node.

There is always an admissable $h$ namely $h(v)= 0$ for all $v$. In this extreme case it becomes Dijkstra's algorithm.

Returning to the example you gave if you plug in the input $A^\*(G,h)$ where $G$ is a description of $G$ and $h = 0$ then $A^\*$ won't halt (geometric series $r = 2 \implies \sum\_i r^i = \frac{1-r^{n+1}}{1-r} \leq 2$ for all finite partial sums). But lets see if we can bypass that; lets try: \begin{equation} h(v) = \begin{cases} 3 & \text{if } v = q\_1 \\ 0 & \text{else}\end{cases} \end{equation} as you can see $h$ is admissible (because $d(q\_1 , \text{goal}) = 3$ on the nose) and $A^\*$ will pick "goal" as its first node (because its two choices are $f(q\_1) = 4$ or $f(\text{goal}) = 2$).
> 4 votes

---
Tags: algorithms, graphs, search-algorithms, a-star-search
---


# Question
Title: Origin of using ">" to represent child in a tree
What are the earliest known uses of the "greater than"/"chevron" symbol (\>) to denote a parent-child relationship in a tree structure? i.e. `parent > child`

e.g.

# Answer
> 2 votes
It comes from set theory. To see that these ideas were around before computers *and that they were explicitly called trees* consider the following famous tree. The convention set theorist *sometimes* use (some use use the convention you gave) is the opposite (the root $\hat{0}$ is the smallest, *i.e.* $\hat{0}\<x$ for all $x\neq \hat{0}$, not the biggest ... this is keeping in line with the equivalence of the principle of induction and the well-ordering principle and is more natural ... *i.e.* a "zero-like" object is the root ... ***I will keep that convention so just replace all of the $\<$ with $\>$ in the proceeding discussion***) The idea is the following:

> **Theorem** From any partial (well)-order we can construct a tree and from any tree we can construct a partial (well)-order.

**Remark** Partial (well)-order is a name I made up so as to artificially distinguish between trees and the relation I am about to define:

Let $P = (V, E) =(V, \leq\_E ) $ be a partial (well)-order then it satisfies the following

1. $(\forall x) \ x \leq x$
2. $(\forall x,y) \ x \leq y \implies y \leq x $
3. $(\forall x,y,z) \ x \leq y \land y \leq z \implies x \leq z $
4. $(\exists \hat{0} )(\forall x) \ \hat{0} \leq x$
5. $(\forall x) \ (\exists 0\_{x} ) \ y \in \\{ t \in V \ | \ t \leq x\\} \implies 0\_{x} \leq y $ ,

The first 3 state that $\leq$ is a partial order and the last states that the predecessor sets are well ordered.

*(Proof of Partial implies Tree)* Let $P = (V, \leq\_E ) $ be a well partial order then connect $v$ to $w$ if $w$ is the least element such that $v \leq w$, *i.e.* $ w = \min \\{x \in V \ | \ v \leq x\\}$ or $w$ ***covers*** v. It is easy to see that there are no cycles (because of rule 3) and that the graph is connected (there is always a path from $\hat{0}$ to any $v$ by induction because $\leq$ is a well order)

*(Proof of Tree implies Partial)* Let $x \leq y$ if there exists a path from $x$ to $y$, it is tedious but easy to see that all of the rules above are satisfied.

***`You may thinking, "man I didn't want an explanation involving set theory"`***

Let me help you dispel those heretical thoughts with the following observations

> **Most of the famous early famous computer scientists got most of their techniques from set theory**

1. The solution to the halting problem is an adaptation of a very beautiful proof by Georg Cantor that there are different sizes of infinity
2. Similarly so is the Entscheidungsproblem
3. Similarly, the proof that exponential time does not equal polynomial time
4. Von Neumann (Von-Neumann architecture) also came up with the Von-Neumann Universe of sets

This should come as no surprise set theory is concerned with the ontological status of the mathematical universe and the idea that all of the objects of our mathematical experience can be constructed via recursion ... and isn't that the big idea behind every algorithm/computer program ... some recursive construction ... trees are the simplest recursively constructed objects other than the natural numbers ... set theory is like a programming language for the platonic realm.

> We can take this whole idea further and prove that every set is a tree and every tree is a set (because of Von Neumann's axiom of regularity) but I will just leave you with the following: set data structures are tree data structures which hopefully will have you convinced of the truly inexorable relationship between the two.

I hope that I have whet your curiosity towards the beauty of sets. Good luck on your mathematical voyages! Bon Voyage!

# Answer
> 1 votes
Here's a usage of "\>" from the 17th century.

https://books.google.com/books?id=771CAAAAcAAJ&pg=PA10#v=onepage&q&f=false

Is this usage just for "greater", though? Consider the text: māĭŏr means ancestor, maioritatis (sometimes majoritatis) here meaning the greater. The left is the greater ancestor, the right the lesser child, and that idea continued to hold true when the set-theoretic definitions of natural numbers were developed in the 19th and early 20th centuries (where smaller numbers are subsets of larger numbers: 0 is the empty set {}, 1 is set of the zero {0}, 2 is the set of 0 and 1 {0,{0}}, etc.) and continued to hold true in our own era when we adopted "\>" to show the drilling down from greater ancestor page to lesser subset child page in web pages and the like. So if we allow that the idea is the same, the first usage of the symbol "\>" for that idea is in the 17th century.

---
Tags: trees, history, syntax
---


title: How to write an OR constraint in MILP?

text:
# Question
Title: How to write an OR constraint in MILP?
I want to write a constraint with ORs in a MILP. In particular, the following:

$$x \ge c \lor x \le -c \lor x=0,$$

where $c$ is just a real number.

Can anyone give me some hints?

# Answer
Tough. You are leaving linear programming.

Solve the problem without these equations and with no restriction for the sign of x. If by coincidence x matches one of the conditions, you are done. Otherwise you will need to solve the problem with one of these equations added.

Calculate how much changing x by eps changes the optimal solution. With that guess how much adding x=0, x\>=c, or x\<=-c would affect the optimal solution. Add the equation that seems to cause the least damage and solve with an optimal goal function G. Then try adding each of the other equations, with an additional restriction goal \>= G.

You could have just tried adding each equation in turn and solving, but this way you might find quicker that one condition can’t lead to an optimal solution. For example if c=100 and your optimal solution was x=80, you can add x\>=100, optimise , and you can likely show easy that x=0 or x\<= -100 will lead to a worse outcome.
> -1 votes

---
Tags: linear-programming, constraint-programming
---


# Question
Title: More the number of for loops greater the problems solved
This is more a formal language theory question.

Imagine a setting where you are given a very basic programming language where variable assignments etc are taken care of without any of the iteration capabilities. The only iteration capability of this primitive language is having a for loop. I'm not sure if there is already such a language defined in literature, if yes, I'd be happy to know its name. Let an instance of this language be called a program. And I think we can understand that a program is usually written to solve a problem or a set or problems that can be solved by the same program with very minor modification to the program for each specific problem.

Now my question is. Let $P\_i$ be the set of problems that can be solved by programs in the given primitive programming language that uses at most $i$ many for loops.

We understand $P\_i \subseteq P\_{i+1}$.

But can we write down a proof of $P\_1 \subset P\_2$? that is prove a separation !

I know this is "too wordy" may be someone can help formalise this question. And if someone can point out to relevant literature that already exists on this problem, it'd be a great help.

Its like the complexity resource being targeted here is the "for loop".

# Answer
Let us consider the LOOP programming language. For a program $f$, denote by $f\_{\max}(n)$ the maximal value of a variable at the end of the program, given that initially, all variables are at most $n$. If $f$ has only one loop then $f\_{\max}(n) = O(n)$. In contrast, using two nested loops you can compute the product function, and the resulting program $g$ satisfies $g\_{\max} = \Theta(n^2)$. This separates $P\_1$ and $P\_2$.

More generally, $f\_{\max}$ can be bounded in terms of the maximum *nesting depth* of loops in $f$. If the maximum nesting depth is $d$, then the growing rate of $f\_{\max}$ is comparable to the $d$th level of the Ackermann hierarchy. This allows us to separate $P\_i$ and $P\_{i+1}$ for every $i$.
> 3 votes

---
Tags: complexity-theory, formal-languages, programming-languages
---


# Question
Title: What time complexity is a reachability algorithm?
I've read there are ways you can determine all reachable pairs using Strongly Connected Components. But, I want to calculate all reachable nodes on the fly - so I don't have to store a massive reachability matrix in RAM. What sort of time complexity would be possible for an algorithm to calculate all reachable nodes in a directed graph, from a single node?

Here's a naive algorithm I came up with, I'm not sure of the time complexity of this. $O(V!)$?

It seems to have an $O(V)$ spacial complexity though.

I've read about the Bellman-Ford algorithm with a time complexity of $O(EV)$ which is essentially $O(V^3)$ and the Floyd-Warshall algorithm which is $O(V^3)$. They require $O(V)$ and $O(V^2)$ space complexity, respectively.

The problem is only inputs can be determined in constant time. So, one would have to find (in $O(V)$ time) all outputs for a particular node. What I actually did in my solution is invert the graph using a similar technique, before running DFS. But I don't know if this is optimal... Also, due to a copy of the graph being stored in memory, my solution has a spacial complexity worse than the bellman-ford algorithm. If this time complexity is also worse, I may as well use bellman fords algorithm

# Answer
> 1 votes
You can calculate all reachable nodes in $O(V+E)$ time and $O(V)$ space, using DFS on the fly.

If you want to use less than $O(V)$ space, then the problem becomes much more challenging. I recommend looking at how the SPIN model checker works. See https://en.wikipedia.org/wiki/Bitstate\_hashing. Even then, the space required is probably still $O(V)$, just with a lower constant factor.

---
Tags: complexity-theory, graphs, time-complexity
---


# Question
Title: Who invented the adder, full-adder, half-adder?
I didn't find, in the digital design books, who invented the adders.

The same person invented the half-adder and the full-adder?

What's the oldest publication on digital arithmetic design?

# Answer
In 1966, I was taught by Professor Tom Kilburn at Manchester University.

He said the half adder was sometimes called the Kilburn adder because he invented it!
> 2 votes

---
Tags: reference-request, arithmetic, memory-hardware, history
---


# Question
Title: Independent set poly reducible to Strongly independent set?
A strongly independent set of a graph $G'$ is a subset $S$ of vertices such that the distance in $G'$ between every two distinct vertices in $S$ is larger than $2$.

It is possible to reduce an instance $\langle G, k\rangle$ of the decision version of independent set to an instance $\langle G', k\rangle$ of the decision version of strongly interdependent set by (1) replacing each edge $e=(u,v)$ of $G$ with two edges $(u, w\_e)$ and $(w\_e, v)$, where $w\_e$ is a new vertex; and (2) connecting all the vertices $w\_e$ with a clique.

In the newly created Graph $G'$, why does adding a middle node prevent us from choosing that node? Basically, how does the reduction step help us?

Solution Notes: http://www.cse.iitd.ernet.in/~amitk/SemI-2015/tut11.pdf

# Answer
Assume that the integer $k$ of the (decision version of the) independent set instance $G$ you are reducing from is larger than $1$ (the case $k \le 1$ is trivial). Let $G'$ be the graph of the corresponding instance of strongly independent set.

As it is written in your solution notes, all the additional vertices are connected to one another with a clique. If you select any of them, say $w\_e$, then you cannot select any other vertex $v$ in $G'$ since the distance in $G'$ between $v$ and $w\_e$ is at most $2$. This implies that the size of a maximum strongly independent set of $G'$ is $1$. Therefore, if there is a strongly independent set of $G'$ of size $k$, it must not include any vertex $w\_e$.

The correctness of the reduction is then easy to see:

* If $S$ is an independent set for $G$, then $S$ is also a strongly independent set for $G'$ since all pairs vertices in $S$ are at a distance of at least $2$ in $G$ and hence they are at distance of at least $4$ in $G'$.
* If $S$ is a strongly independent set for $G'$ with $|S| \ge k$, then $S$ cannot include any vertex $w\_e$, and is therefore a subset of the vertices of $G$. The distance between any two distinct vertices in $S$ is larger than $2$ in $G'$, and hence it is larger than $1$ in $G$.
> 2 votes

---
Tags: np-complete, np
---


# Question
Title: why swap function is use in union find algorithm? How rank or size array is used for optimization
```
void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (size[a] < size[b])
            swap(a, b);
        parent[b] = a;
        size[a] += size[b];
    }
}

```

Q1.why we need this swapping? can't we do like this without swapping

```
if (size[a] < size[b])

        parent[a] = b;
        size[b] += size[a];

```

Q2.what is the difference between size array and rank array.Is Rank means the height of a node and size means no of node in that tree which contains this node

# Answer
To answer your first question, it is a matter of style. If you do it your way, then the code appears twice. Code duplication is more prone to bugs, since you have to duplicate every change that you make, taking care (in this case) to switch $a$ and $b$.
> 0 votes

---
Tags: graphs, union-find
---


title: Language of particular CFG

text:
# Question
Title: Language of particular CFG
Let: $ G = \<V, \Sigma, R, S \>: \\ V = \\{ S,A,B,C \\} \\ \Sigma = \\{0, 1\\} \\ R: \\ S \to CSC|A \\ A \to 0B1|1B0 \\ B \to CB|\epsilon\\ C \to 1|0 $

I need to find the language (no need to formally prove). I have written many words but cannot seem to find a rule. After trying that path I rewrote the grammar in a shorter rules:

$$ S \to 0S0|0S1|1S0|1S1|0B1|1B0 \\ B \to 1B|0B|\epsilon $$

What should be my way of finding any pattern? to go each possible path independently ?

# Answer
> 2 votes
First, let us notice the following: $$ L(S) = \\{ xyz \mid x,z \in \\{0,1\\}^\*, |x|=|z|, y \in L(A) \\} \\ L(A) = 0L(B)1 \cup 1L(B)0 \\ L(B) = (0+1)^\* $$ Putting everything together, we get $$ L(G) = \\{ x\sigma y \tau z \mid x,y,z \in \Sigma^\*, \sigma,\tau \in \Sigma, |x|=|z|, \sigma \neq \tau \\} $$ In other words, a word $w$ is in the language if there exists $i \leq |w|/2$ such that the $i$th symbol from the left is different from the $i$th symbol from the right. The condition $i \leq |w|/2$ can be eliminated, and we get that for some $i$, the $i$th symbol of $w$ is different from the $i$th symbol of $w^R$. In other words, $w \neq w^R$.

So your grammar generates the language of non-palindromes.

---
Tags: formal-languages, context-free, formal-grammars
---


title: Complexity of linear programming

text:
# Question
Title: Complexity of linear programming
I have a basic question, if I can model a problem $(P)$ by a linear program, can we say that $(P)$ is polynomial?

Linear programs can be solved using simplex, and it was proved that simplex run in exponential time for some instances, so why some references assume that linear programming is polynomial?

# Answer
There exist polynomial time algorithms for solving linear programs. These include the ellipsoid algorithm and interior-point methods. See Wikipedia.
> 3 votes

# Answer
It's because there are other algorithms (like interior point methods) which run in polynomial time for solving the problem. Even with that being said, it is perfectly possible that the simplex method will outperform them in practice.
> 3 votes

---
Tags: complexity-theory, linear-programming
---


# Question
Title: Find combination of vectors from array that sum up to s
I have an array of $n$ $m$-dimensional vectors (in my case, they're 27 dimensional). I also have an $m$-dimensional vector $s$. I want to find all combinations of $k$ vectors from my array whose vector sum is equal to $s$. How to do this efficiently?

The best I could do is just a brute force which is $O(n^k)$ and impossibly slow.

Any help is appreciated.

# Answer
> 2 votes
If $k$ if fixed, you cannot do much better than enumerating all subsets of vectors.

$\binom{n}{k} = \Omega\big((\frac{n}{k})^k\big)$ is a lower bound in general. Let all input vectors be equal to $(1,1, \dots,1)$ and let $s=(k, \dots, k)$. There are $\binom{n}{k} \ge (\frac{n}{k})^k$ distinct sets of $k$ vectors that satisfy your property.

# Answer
> 3 votes
If $k$ is part of the input, the problem is NP-complete even when $m=1$ (and when we want to know if there's even a single solution). That is, when $m=1$, we essentially have a collection of $n$ values and our task is to decide if there is a subset of those that sum up to a target $s$. This is known as subset sum.

The Wikipedia page lists algorithms that you might be able to adapt to your more general case as well. Also, if $k$ is small enough, you might be able to do something better.

---
Tags: algorithms, arrays
---


title: Maximize the sum of chosen numbers

text:
# Question
Title: Maximize the sum of chosen numbers
I have 2 problems that derive from a simple problem. I'll explain the simple one with the solution I found and after that the modified problem.

> Suppose there is a game with 2 players, A and B and a list of positive integers. Player A starts by taking out a number from the list, player B does the same and so on after the there are no longer numbers in the list. Both players sum up the picked numbers. Each player scores the difference between his sum and the opponent's one. The question is what is the maximum score player A can obtain if both players play in an optimal manner.

Now, for this I figured out that the optimal strategy for each player is to take the biggest number at each step.

The following 2 modification:

> At the beginning of the game player A should remove K numbers from the list. If he does this in an optimal manner and after that the games is the initial one, what is the maxim score he can obtain?

and

> At each step the players can pick the left-most or the right-most number from the list. Again they play in an optimal manner. Which is the maximum score player A can obtain?

For the second modification I can think of a brute-force approach, i.e. computing the tree of all possibilities, but this does not work for big input data. I believe that there is some kind of DP algorithm.

For the first modification I can't think of an idea.

Can someone help with some ideas for the 2 modifications, what algorithm to design in order to get the response?

\[LATTER EDIT\]

For the second variation I found the DP solution at https://www.geeksforgeeks.org/optimal-strategy-for-a-game-dp-31/

# Answer
> 1 votes
The first modification can be solved with dynamic programming.

In the original problem, given N numbers $x\_1$ to $x\_N$, the optimal strategy for both sides is to always take the largest number (this is not trivial to prove, but not difficult either). Since there is no restriction which number to pick we may assume $x\_1 ≥ x\_2 ≥ ... ≥ x\_N$.

Now let f(k, n) be the optimal score that can be achieved if we use the first n numbers only, and remove k of those in an optimal way (k ≤ n). We are therefore looking for f(K, N). f(0, n) is easily calculated by adding and subtracting $x\_i$ in turn.

If we look for f(k, n), k ≥ 1: If k = n then we remove all of the first n numbers, so f(k, n) = 0. If k \< n: We take the first n numbers, then remove k of those. Either we remove k of the first n-1 numbers and keep $x\_n$, or we remove k-1 of the first n-1 numbers, then remove $x\_n$, and we pick whatever is better.

In the first case, the score is f(k, n-1) and then we add or subtract $x\_n$, depending on whether n-k is even or odd. The score is f(k, n-1) + $x\_n$ if n-k is odd, and f(k, n-1) - $x\_n$ if n-k is even.

In the second case, since $x\_n$ is removed, the score is f(k, n) = f(k-1, n-1). All in all:

If n-k is odd then f(k, n) = max(f(k, n-1) + $x\_n$, f(k-1, n-1)). If n-k is even then f(k, n) = max(f(k, n-1) - $x\_n$, f(k-1, n-1)). And the final result is f(K, N).

If we change it to "remove up to K numbers" then the result is the largest of f(i, N) for 0 ≤ i ≤ K.

# Answer
> 1 votes
Here is the post for the 2nd modification, which is

> At each step the players can pick the left-most or the right-most number from the list. Again they play in an optimal manner. Which is the maximum score player A can obtain?

The solution is based on DP. For the sub-problem (i-j) i.e. `v[]i, v[i+1], ..., v[j]` there are two choices:

1. The user chooses the i-th element with value v\[i\]: The opponent either chooses (i+1)-th element or j-th element. The opponent intends to choose the element which leaves the user with minimum value. i.e. The user can collect the value `v[i] + min(F(i+2, j), F(i+1, j-1))`

2. The user chooses the j-th element with value v\[j\]: The opponent either chooses i-th element or (j-1)-th element. The opponent intends to choose the element which leaves the user with minimum value. i.e. The user can collect the value `v[j] + min(F(i+1, j-1), F(i, j-2))`

Following is recursive solution that is based on above two choices. We take the maximum of two choices.

> F(i, j) represents the maximum value the user can collect from i-th coin to j-th coin.
>
> F(i, j) = Max(v\[i\] + min(F(i+2, j), F(i+1, j-1)), v\[j\] + min(F(i+1, j-1), F(i, j-2)))
>
> Base Cases
>
> F(i, j) = v\[i\] If j == i
>
> F(i, j) = max(v\[i\], v\[j\]) If j == i+1

Here is a pice of code in Python that solves it

```
def optimalStrategyOfGame(arr, n):

    # Create a table to store solutions of subproblems
    table = [[0 for i in range(n)] for i in range(n)]

    # Fill table using above recursive formula. Note that the table is
    # filled in diagonal fashion from diagonal elements to table[0][n-1] which is the result.
    for gap in range(n):
        for j in range(gap, n):
            i = j - gap

            # Here x is value of F(i+2, j), y is F(i+1, j-1) and z is
            # F(i, j-2) in above recursive formula
            x = 0
            if((i + 2) <= j):
                x = table[i + 2][j]
            y = 0
            if((i + 1) <= (j - 1)):
                y = table[i + 1][j - 1]
            z = 0
            if(i <= (j - 2)):
                z = table[i][j - 2]
            table[i][j] = max(arr[i] + min(x, y), arr[j] + min(y, z))
    return table[0][n - 1]

```

\[SOURCE\] https://www.geeksforgeeks.org/optimal-strategy-for-a-game-dp-31/

---
Tags: algorithms, greedy-algorithms
---


# Question
Title: Detecting conservation, loss, or gain in a crafting game with items and recipes
Suppose we're designing a game like *Minecraft* where we have lots of items $i\_1,i\_2,...,i\_n\in I$ and a bunch of recipes $r\_1,r\_2,...,r\_m\in R$. Recipes are functions $r:(I\times\mathbb{N})^n\rightarrow I\times\mathbb{N}$, that is they take some items with non-negative integer weights and produce an integer quantity of another item.

For example, the recipe for cake in *Minecraft* is:

3 milk + 3 wheat + 2 sugar + 1 egg $\rightarrow$ 1 cake

... and the recipe for torches is:

1 stick + 1 coal $\rightarrow$ 4 torches

Some recipes could even be reversible, for example: 9 diamonds $\leftrightarrow$ 1 diamond block

If there's some combination of recipes we can repeatedly apply to get more of the items that we started with then the game is poorly balanced and this can be exploited by players. It's more desirable that we design the game with recipes that conserve items or possibly lose some items (thermodynamic entropy in the real world - you can't easily un-burn the toast).

**Is there an efficient algorithm that can decide if a set of recipes will:**

* conserve items?
* lose items to inefficiency?
* gain items?

**Is there an efficient algorithm that can find the problematic recipes if a game is imbalanced?**

My first thoughts are that there is a graph structure / maximum flow problem here but it's very complex, and that it resembles a knapsack problem. Or maybe it could be formulated as a SAT problem - this is what I'm considering to code it at the moment but something more efficient might exist.

We could encode recipes in a matrix $\mathbf{R}^{m \times n}$ where rows correspond to recipes and columns correspond to items. Column entries are negative if an item is consumed by a recipe, positive if it's produced by the recipe, and zero if it's unused. Similar to a well known matrix method for graph cycle detection, we could raise $\mathbf{R}$ to some high power and get sums of each row to see if item totals keep going up, stay balanced, or go negative. However, I'm not confident this always works.

Any discussion, code, or recommended reading is very appreciated.

# Answer
This should be solvable with linear programming.

# Background and setup

Let the state vector be a vector of the count of number of each item you have. If the possible items are milk, wheat, sugar, egg, cake, diamonds, then the rule

3 milk + 3 wheat + 2 sugar + 1 egg $\rightarrow$ 1 cake

affects the state vector by adding $(-3,-3,-2,-1,1,0)$ to it. So, let $a\_i$ denote the change vector for the $i$th rule.

# Gaining items

I claim that there exists a way to gain items without bound iff there exists a feasible solution to the linear program

$$a\_1 x\_1 + \dots + a\_n x\_n \ge (0,0,\dots,0), x\_1 \ge 0, \dots, x\_n \ge 0$$

such that $a\_1 x\_1 + \dots + a\_n x\_n\>(0,0,\dots,0)$. Here $\ge$ is defined on vectors pointwise (i.e., $u \ge v$ iff $u\_i\ge v\_i$ holds for all $i$) and similarly for $\>$. This can be expressed as a linear program: you maximize the sum of the coordinates of $a\_1 x\_1 + \dots + a\_n x\_n$, subject to the inequalities above. Therefore, you can solve it in polynomial time using a linear programming solver. This tells you whether there is a way to gain some item without bound.

Why is the claim true? Well, if there is a feasible solution to the linear program, then it provides a way to grow the number of some item without bound. In particular, if you start with a very large number of each item, then apply rule 1 $x\_1$ times, rule 2 $x\_2$ times, etc., you'll end up with a new state vector that differs from where you started by $a\_1 x\_1 + \dots + a\_n x\_n$, which is at least as large in each component and is strictly larger in at least one component. Moreover, if you start with a sufficiently large number of items, you'll never "go negative" at any intermediate step of application of the rules. Note that if there is a solution to this linear program, there is a solution in the rationals, which yields a solution in the integers (multiply by the appropriate constant to clear denominators).

Conversely, if there is a method to grow the number of some item without bound, then there is a solution to the linear program: just let $x\_i$ count the number of times rule $i$ is applied in that method, and you'll see that this yields a valid solution to the linear program.

# Losing items

I believe that there is a similar equivalence: there exists a way to lose items without bound iff there exists a feasible solution to the linear program

$$a\_1 x\_1 + \dots + a\_n x\_n \le (0,0,\dots,0), x\_1 \ge 0, \dots, x\_n \ge 0$$

such that $a\_1 x\_1 + \dots + a\_n x\_n\<(0,0,\dots,0)$. You should check my reasoning as I have not checked this carefully.

# Conservation

Finally, if there is no way to gain items without bound or lose items without bound, then I think it follows that value is conserved.
> 3 votes

# Answer
Your problem is equivalent to asking whether there is some linear combination of row vectors from your $\mathbb R^{m\times n}$ matrix that has all coefficients positive and sums to a vector in which (a) every element is $\ge 0$ and (b) at least one element is $\> 0$.

(Notice that the *order* of the operations doesn't matter: Running them in some order might cause the quantity of some item to dip below zero, but we can just look for the low-water-mark and suppose that we have at least that many of each item to start with.)

I think this can be solved by linear programming: Make a variable for each coefficient, add $\ge 0$ constraints for each element in the output vector (each element is a dot product of coefficient variables and constant coefficients from recipes), more $\ge 0$ constraints for each coefficient variable, and set the function to maximise to be the sum of all elements. To make it bounded, set the sum of coefficient variables to some constant, e.g. 1. Iff the solution value is $\> 0$, you have non-conservation!

Note that fractional values are not an issue: They must be rational, so you can always multiply through by all denominators to get a pure-integer solution.
> 4 votes

---
Tags: graphs, optimization, knapsack-problems, integer-programming, computer-games
---


# Question
Title: Is physical pages zeroed out before it's mapped to a virtual page?
I don't how this works. According to me if the physical memory is not cleared then there is some security risk as there may be some sensitive information in it from the other processes. How does the kernel take care of this?

# Answer
> 2 votes
Yes, the kernel zeroes out pages before allocating them to a user-level process. The details depend on the specific operating system; some may zero it out when the page is needed, others might run a separate thread that periodically zeroes out pages in anticipation that they'll be allocated.

---
Tags: operating-systems, virtual-memory, paging
---


title: What is the meaning of $O(m+n)$?

text:
# Question
Title: What is the meaning of $O(m+n)$?
This is a basic question, but I'm thinking that $O(m+n)$ is the same as $O(\max(m,n))$, since the larger term should dominate as we go to infinity? Also, that would be different from $O(\min(m,n))$. Is that right? I keep seeing this notation, especially when discussing graph algorithms. For example, you routinely see: $O(|V| + |E|)$ (e.g. see here).

# Answer
You are right. Notice that the term $O(n+m)$ slightly abuses the classical big-O Notation, which is defined for functions in **one** variable. However there is a natural extension for multiple variables.

Simply speaking, since $$ \frac{1}{2}(m+n) \le \max\\{m,n\\} \le m+n \le 2 \max\\{m,n\\},$$ you can deduce that $O(n+m)$ and $O(\max\\{m,n\\})$ are equivalent asymptotic upper bounds.

On the other hand $O(n+m)$ is different from $O(\min\\{n,m\\})$, since if you set $n=2^m$, you get $$O(2^m+m)=O(2^m) \supsetneq O(m)=O(\min\\{2^m,m\\}).$$
> 39 votes

# Answer
Believe it or not, it seems (in my experience) that many algorithms people have actually not thought about what the big O notation formally means, and when asked about it, you can get several different answers. Some issues are discussed in the paper On Asymptotic Notation with Multiple Variables by Rodney R. Howell.

Curiously, it also seems that most introductory algorithms courses spend lots of time being very formal about big O notation with a single variable, and then the next weeks happily use the notation for graph algorithms with several variables in a casual way, without discussing what the notation actually means.
> 34 votes

# Answer
# Part 1

I'm going to do something I decided I wouldn't do: try to nutshell my research on this topic. I'll go over on how the algorithmic O-notation *must* be defined, why it is probably not what you've been taught, and what other misconceptions float around this topic. I wrote this in the form of an imaginary discussion.

The following discussion is based on the following papers:

## Notation

We will the use the following notation:

$$ \newcommand{\TR}{\mathbb{R}} \newcommand{\TN}{\mathbb{N}} \newcommand{\subsets}\[1\]{\mathcal{P}(#1)} \newcommand{\setb}\[1\]{\left\\{#1\right\\}} \newcommand{\land}{\text{ and }} \begin{aligned} & \text{Symbol} && \text{Meaning} && \text{Example} \\ & \text{ } && \text{ } && \text{ } \\ & \TN && \text{Natural numbers} && 0, 1, 2, 3, \dots \\ & \TR && \text{Real numbers} && -3, 0, 1.5, \pi, \dots \\ & X \to Y && \text{Functions from set X to set Y} && \TR \to \TR \\ & \subsets{X} && \text{Subsets of set X} && \subsets{\setb{0, 1}} = \setb{\emptyset, \setb{0}, \setb{1}, \setb{0, 1}} \\ & R\_X && \text{Cost functions in set X} && X \to \TR^{\geq 0} \\ & f|A && \text{Restriction of function f to set A} \end{aligned} $$

## Cost-functions

A *cost-function* in a set $X$ is an element of the set

$$ R\_X = X \to \TR^{\geq 0}, $$

the set of all functions from $X$ to non-negative real numbers. Consider an algorithm whose input-set is $X$. The resource-consumption of that algorithm, for a given resource, is a function $f \in R\_X$, where $f(x)$ returns the amount of resources the algorithm spends on input $x \in X$.

For example, a graph algorithm may take a graph over a set $V$ as an input. Then the input-set $X$ is the set of all graphs over $V$, and $f(x)$ is the amount of resources the algorithm spends on graph $x \in X$.

### Shouldn't the parameter of a cost-function be an input-size?

No. Input-size does not make sense as a general concept. The mapping from the input-set is the most detailed characterization of the resourse-consumption of an algorithm.

### How do you obtain cost-functions?

To obtain a cost-function of an algorithm, you specify the model of computation --- e.g. an abstract state machine together with its atomic instructions --- and assign the atomic instructions their cost-functions. These atomic cost-functions imply a cost-function for each algorithm as a sum of the cost-functions of the instructions that are executed for a given input.

By assigning the atomic cost-functions, you are making a decision on what to measure. You may first analyze a specific resource, and later change the atomic cost-functions when you want to measure something else. Note that 0 is also a valid cost for a given input.

### How do you work with cost-functions?

Let $f, g \in R\_X$, and $c \in \TR^{\> 0}$. We will be writing things such as $g \leq c f$. But what does this mean?

If $\ominus : \TR^{\geq 0} \to \TR^{\geq 0}$ is a unary function, we lift it to $R\_X$ by

$$(\ominus f)(x) = \ominus f(x).$$

If $\odot : \TR^{\geq 0} \times \TR^{\geq 0} \to \TR^{\geq 0}$ is a binary function, we lift it to $R\_X$ by

$$(f \odot g)(x) = \odot(f(x), g(x)) = f(x) \odot g(x).$$

If $\mathord{\sim} \subset \TR^{\geq 0} \times \TR^{\geq 0}$ is a relation in $\TR^{\geq 0}$, we lift it to $R\_X$ by

$$f \sim g \iff \forall x \in X: f(x) \sim g(x).$$

To summarize, operations on $\TR^{\geq 0}$ are lifted to $R\_X$ elementwise. We then have

$$f \leq c g \iff \forall x \in X : f(x) \leq c g(x).$$

### How do you work with sets of cost-functions?

Let $F, G \subset R\_X$. We lift the operations on $\TR^{\geq 0}$ to $\subsets{R\_X}$ by

$$ \begin{aligned} \ominus F & = \setb{\ominus f : f \in F}, \\ F \odot G & = \setb{f \odot g : f \in F \land g \in G}. \\ \end{aligned} $$

## Algorithmic O-notation

The *algorithmic O-notation* is the proper class of functions

$$O = \setb{O\_X : R\_X \to \subsets{R\_X} : X \text{ is a set}},$$

where

$$O\_X(f) = \setb{g \in R\_X : \exists c \in \TR^{\> 0} : g \leq c f}.$$

For the expression inside the set-builder notation, we say that $g$ is linearly dominated by $f$, or $f$ linearly dominates $g$. Correspondingly, algorithmic O-notation is also called *linear dominance*.

### There is a separate $O\_X$ for each input-set $X$?

Yes. And all of these infinite number of set-specific O-notations must be consistent with each other. The O-notation is the proper class of those set-specific O-notations, not just one specific $O\_X$ for a single set $X$. Also, the domain-set $X$ is important; remove it and you may end up in incorrect conclusions because of confusing your domain.

### This is not what I've been taught?

The books and courses are currently using an incorrect formalization of algorithmic O-notation; give it some time.

### What do you mean by incorrect formalization?

In the same way that iceskaters have a strong idea about what iceskating should look like, computer scientists have a strong idea about what algorithmic O-notation should look like.

Current formalizations of algorithmic O-notation in books and courses conflict with that idea.

### Can you give a concrete example of this?

Let

$$\mathcal{F} = \setb{\setb{x \in \TN^2 : x \geq x\_0} : x\_0 \in \TN^2}$$

Introduction to Algorithms, 2nd. ed, page 50, formalizes O-notation in $\TN^2$ as:

$$ f \in O'\_{\TN^2}(g) \iff \exists c \in \TR^{\>0}, \exists A \in \mathcal{F}: f|A \leq c(g|A). $$

Let $f \in R\_{\TN}$ be an arbitrary cost-function. Suppose $G : \TN^2 \to \TN$ is an algorithm with cost-function $g \in R\_{\TN^2}$ such that $g(x, 0) = f(x)$, and $g(x, y) = 0$ when $y \> 0$. Then $g \in O'\_{\TN^2}(0)$; seems like a cheap algorithm to call. Create an algorithm $F: \TN \to \TN$ which computes $F(x) = G(x, 0)$ by calling $G$. Then $F$ has cost-function $f$. Hence, the O-set of $g$ does not tell you anything about how costly it is to call $G$.

### How do you know that a formalization captures the idea of O-notation?

When the O-notation is formalized as linear dominance, you have a simple way to check whether a function is in an O-set. However, from this form it is hard to see whether it captures the right idea. Simply picking some version of local linear dominance as formalization is just guessing.

The solution is to approach formalization from a different viewpoint: simply write down the rules how you expect O-notation to work, and see what you get. A natural way to do this is to provide a set of equations which describe how O-notation preserves structure (see the cheat-sheet below).

After this is done, those equations are then up to discussion for the community: do they really capture the right idea? To facilitate this discussion, the equation-set is best made minimal, so that there are no redundant equations. For example, the cheat-sheet below is very redundant. However, they contain an equivalent minimal subset of 6 equations. Linear dominance falls out naturally from this equation-set. I'll come back to this.

### Isn't some kind of asymptotic behavior essential to O-notation?

No. It is the scale-invariance ($c$) which in some cases allows to ignore a finite number of elements in the domain.

### Isn't the O-notation used in mathematics defined differently?

Yes. There are multiple different concepts of O-notation, and each is used in a different context and different purpose. Most of them are a version of local linear dominance which we will come back to later. The O-notations most often seen in mathematics (e.g. series, approximation, convergence) localize to the neighorhoods of a single point, or to the neighborhoods of infinity. We concentrate on the algorithmic O-notation, which is used to analyze algorithms, and which does not use any localization. This is because in the context of algorithm analysis, every part of a cost-function is important!

## Basic usage

### Can I write $O\_{\TN}(n^2)$?

Yes. It is clear what the implied function is.

### Can I write $O(n^2)$?

No. It is not clear what the implied function is, because the domain is not known. For example, it could be any subset of integers, or even a subset of $\TN^2$. The domain matters.

### Can I write $O\_{\TN^2}(nm^2)$?

Yes, but with caution. In particular, you must first define an implicit ordering for the parameters; say an alphabetical order. Then $nm^2$ stands for $f \in R\_{N^2}$ such that $f(m, n) = nm^2$, rather than $f(n, m) = nm^2$. These functions are different.

### Can I write $O\_{\TN^2}(n^2)$?

No. It is not clear whether $n$ refers to the first argument or the second argument. This case can be disambiguated by $O\_{\TN^2}((m, n) \mapsto n^2)$.

### Is $O\_{\TN^2}((m, n) \mapsto n^2) = O\_{\TN}(n^2)$?

No; the functions have different domains.

## How do I use the O-notation?

Use the following cheat-sheet for the O-notation. It's like the rules for differentiation; you strive to develop a sufficiently large rule-set to avoid needing to use the definition directly ever again. Suppose $X$, $Y$, and $Z$ are sets, $\alpha, \beta \in \TR^{\> 0}$, $f, g, u, v \in R\_X$, $s : Y \to X$, and $C \subset \subsets{X}$ is a finite cover of $X$.

$$ \begin{aligned} & \text{Property} && \text{Definition} \\ & \text{ } && \text{ } \\ & \text{Order-consistency} && f \leq g \implies f \in O\_X(g) \\ & \text{Reflexivity} && f \in O\_X(f) \\ & \text{Transitivity} && (f \in O\_X(g) \land g \in O\_X(h)) \implies f \in O\_X(h) \\ & \text{Orderness} && f \in O\_X(g) \iff O\_X(f) \subset O\_X(g) \\ & \text{Zero-separation} && 1 \not\in O\_{\TN^{\>0}}(0) \\ & \text{One-separation} && n \not\in O\_{\TN^{\>0}}(1) \\ & \text{Zero-triviality} && O\_X(0) = \setb{0} \\ & \text{Scale-invariance} && O\_X(\alpha f) = O\_X(f) \\ & \text{Bounded translation invariance} && O\_X(f + \beta + \alpha) = O\_X(f + \beta) \\ & \text{Power-homogeneity} && O\_X(f)^{\alpha} = O\_X(f^{\alpha}) \\ & \text{Additive consistency} && u O\_X(f) + v O\_X(f) = (u + v)O\_X(f) \\ & \text{Multiplicative consistency} && O\_X(f)^u O\_X(f)^v = O\_X(f)^{u + v} \\ & \text{Locality} && (\forall D \in C : (f|D) \in O\_D(g|D)) \implies f \in O\_X(g) \\ & \text{Scalar homogeneity} && \alpha O\_X(f) = O\_X(\alpha f) \\ & \text{Homogeneity} && u O\_X(f) = O\_X(u f) \\ & \text{Multiplicativity} && O\_X(f) O\_X(g) = O\_X(fg) \\ & \text{Restrictability} && O\_X(f)|D = O\_D(f|D) \\ & \text{Additivity} && O\_X(f) + O\_X(g) = O\_X(f + g) \\ & \text{Summation rule} && O\_X(f + g) = O\_X(\max(f, g)) \\ & \text{Maximum rule} && \max(O\_X(f), O\_X(g)) = O\_X(\max(f, g)) \\ & \text{Maximum-sum rule} && \max(O\_X(f), O\_X(g)) = O\_X(f) + O\_X(g) \\ & \text{Sub-composability} && O\_X(f) \circ s \subset O\_Y(f \circ s) \\ & \text{Injective super-composability} && O\_X(f) \circ s \supset O\_Y(f \circ s) (s \text{ injective}) \end{aligned} $$

### Shouldn't translation invariance hold also when $\beta = 0$?

No. Otherwise it would be possible for a cost-function $f \in R\_X$ with $f(x) = 0$ for some $x \in X$ to be equivalent to another cost-function $f' \in R\_X$ with $f'(x) \neq 0$. For example, we would have $O(1) = O(0)$ which are fundamentally different classes of cost-functions.

## Why would this formalization be correct?

Perhaps because you can prove that the algorithmic O-notation is exactly the proper class of functions $\setb{O\_X : R\_X \to \subsets{R\_X} : X \text{ is a set}}$ which satisfy the following properties:

* Order-consistency
* Transitivity
* One-separation
* Scale-invariance
* Sub-composability
* Sub-homogeneity (it's the same as homogeneity but with $\subset$ rather than $=$)

Questioning the validity of the formalization is equivalent to questioning the validity of these properties. Let's go over them.

The first two properties --- order-consistency and transitivity --- state that $f \in O\_X(g)$ is a preorder relation which is consistent with pointwise comparison. One-separation says that not every function can be equivalent. Scale-invariance is the very reason you are defining the O-notation in the first place; acceleration by a constant is algorithmically boring. No-one probably objects to these; they are at the core of any formalization of O-notation in any context.

The last two --- sub-composability and sub-homogeneity --- are what makes this O-notation *algorithmic*. Sub-composability says that the O-notation preserves composition, which means that things still work even if you refactor a part of your algorithm to a sub-algorithm. Sub-homogeneity says that the O-notation preserves repetition, which means that things still work even if you repeat things in a loop.

### Anything else to say about those properties?

There are no other formalizations of O-notation which satisfy the listed properties; algorithmic O-notation is uniquely defined. It can also be proved that the property-set above is minimal; for any of these properties, there exists an "O-notation" which breaks exactly that property and satisfies the others. Since the algorithmic O-notation satisfies these properties, they are not inconsistent either.

### Any other ways to characterize linear dominance?

Linear dominance is the only formalization of O-notation which has the property that the following two modes of analysis always produce the same result:

* Carry out the cost-analysis exactly by performing a sequence of structure-preserving operations on cost-functions. Then compute the O-set of the final result. Matrix algorithms are often analyzed this way.
* Compute the O-sets of the atomic cost-functions, and carry out the cost-analysis of an algorithm purely in terms of O-sets, performing exactly the same operations to the O-sets as in the exact case. This is the usual way of analyzing algorithms.

Given any other formalization, it is possible to construct an instance of analysis where the two modes do not produce the same result.

## Related notations

The related notations are

$$ \begin{aligned} o\_X(f) & = \setb{g \in R\_X : g \in O\_X(f) \land f \not\in O\_X(g)}, \\ \Omega\_X(f) & = \setb{g \in R\_X : f \in O\_X(g) }, \\ \omega\_X(f) & = \setb{g \in R\_X : f \in O\_X(g) \land g \not\in O\_X(f)}, \\ \Theta\_X(f) & = \setb{g \in R\_X : g \in O\_X(f) \land f \in O\_X(g)}. \end{aligned} $$

Notice how the O-notation determines them all.

### How do I use the related notations?

Convert back and forth between the O-notation and them using the above definitions, and derive analogous cheat-sheets for them. Left as an exercise!

## Limit form

The notations can also be given in the following limit form. Let

$$ \begin{aligned} F & = \setb{x \in X : f(x) \> 0}, \\ G & = \setb{x \in X : g(x) \> 0}. \end{aligned} $$

Then

$$ \begin{aligned} f \in O\_X(g) & \iff \sup \frac{f|F}{g|F} \< \infty, \\ f \in o\_X(g) & \iff \sup \frac{f|F}{g|F} \< \infty \land \inf \frac{f|G}{g|G} = 0, \\ f \in \Omega\_X(g) & \iff \inf \frac{f|G}{g|G} \> 0, \\ f \in \omega\_X(g) & \iff \inf \frac{f|G}{g|G} \> 0 \land \sup \frac{f|F}{g|F} = \infty, \\ f \in \Theta\_X(g) & \iff \sup \frac{f|F}{g|F} \< \infty \land \inf \frac{f|G}{g|G} \> 0. \end{aligned} $$

Here we use the convention that $x/0 = \infty$ for each $x \in \TR^{\> 0}$. The restrictions are needed to avoid the case $0/0$.

### Where is the limit in that?

I'll get back to this.

### The definitions for $o$ and $\omega$ do not look familiar?

The formalizations of the $\omega$ and $o$-notations are also currently incorrect in books and courses; any other choice than the above is inconsistent with the O-notation.

This *sufficient* condition for $o$ might look more familiar:

$$ \begin{aligned} {} & \forall c \in \TR^{\>0}: f \leq cg \\ \iff & \sup \frac{f|F}{g|F} = 0 \\ \implies & f \in o\_X(g). \end{aligned} $$

Similarly for $\omega$:

$$ \begin{aligned} {} & \forall c \in \TR^{\>0}: g \leq cf \\ \iff & \inf \frac{f|G}{g|G} = \infty \\ \implies & f \in \omega\_X(g). \end{aligned} $$

## Preorders

Let

$$f \preceq\_X g \iff f \in O\_X(g).$$

Then $\preceq\_X$ is a preorder in $R\_X$; i.e. a reflexive and transitive relation in $R\_X$. A preorder generalizes a partial order in that there can be multiple elements equivalent to each other. The notations then become

$$O\_X(f) = \setb{g \in R\_X : g \preceq\_X f },$$

$$o\_X(f) = \setb{g \in R\_X : g \prec\_X f },$$

$$\Omega\_X(f) = \setb{g \in R\_X : g \succeq\_X f },$$

$$\omega\_X(f) = \setb{g \in R\_X : g \succ\_X f },$$

$$\Theta\_X(f) = \setb{g \in R\_X : g \approx\_X f }.$$

That is, we may as well define the O-notation in a set $X$ as a preorder.

### I've seen this analogue before!

Right, but it is not merely an analogue; it is an exact correspondence; an alternative view. It is possible to go back and reframe all of the discussion this far in terms of preorders, rather than O-notation. In terms of the preorders, $O\_X(f)$ is a principal down-set of $\preceq\_X$. Conversion of the cheat-sheet to preorder-form is left as an exercise.

### Perhaps non-principal down-sets of $\preceq\_X$ are relevant too?

That's right. I'll get back to this.

## Worst/best/average case analysis

A *grouping* of set $X$ is a function $g : X \to Z$, where $Z$ is a set. For example, if your input-set $X$ is the set of all graphs over set $V$, you may take a function $g : X \to \TN^2$ which maps each graph $x \in X$ to a pair of integers $(n, m) \in \TN^2$, denoting the number of vertices and edges in that graph.

### Why is it called a grouping?

The preimage $g^{-1}(\setb{z})$, where $z \in g(X)$, gives all the input-elements $x \in X$ which $g$ maps to the same property $z$; these preimages partition, or group, the input-set $X$. For the graph grouping example, $g^{-1}(\setb{(n, m)})$ gives all the graphs with $n$ vertices and $m$ edges.

### Shouldn't a grouping be defined as surjective?

You could do that, but that definition would be harder to use (in my opinion). For example, in the graph grouping example, I could simply map to $\TN^2$, even if the graph-set does not contain graphs with all combinations of vertices and edges.

### What is an extended cost-function?

An *extended cost-function* in a set $X$ is an element of $R^{\infty}\_X = X \to (\TR^{\geq 0} \cup \setb{\infty})$.

### What is worst-case analysis?

A *worst-case analysis* of $f \in R\_X$ over a grouping $g : X \to Z$ is the study of $f^\* \in R^{\infty}\_{g(X)}$ such that $f^\*(z) = \sup f(g^{-1}(\setb{z}))$, or some $O$-set which contains it.

### What is a case?

A *case* over a grouping $g : X \to Z$ is a right-inverse of $g$. That is, a function $s : g(X) \to X$ such that $g \circ s = id\_{g(X)}$.

### What is a worst case?

A case $s : g(X) \to X$ over a grouping $g : X \to Z$ is called *worst* of $f \in R\_X$, if

$$(f \circ s)(z) = \sup f(g^{-1}(\setb{z})).$$

A worst case may not exist. If it does though, then the worst-case analysis of $f$ over $g$ is essentially about studying the cost-function of an auxiliary algorithm which, given $(n, m)$, forwards the worst case $s(n, m)$ to the original algorithm.

For the graph grouping example, the worst case of $f$ over $g$ exists because the preimages (*groups*) are finite (assuming finite $V$).

### What is best-case analysis and a best case?

The terms *best-case analysis*, and *best case*, are defined otherwise exactly as the worst case, but supremum is replaced with infimum, and $O$-set is replaced with $\Omega$-set.

### What is average-case analysis?

Left as an exercise:p

Due to character count limitation, we'll continue in another answer...
> 15 votes

# Answer
# Part 2

$$ \newcommand{\TR}{\mathbb{R}} \newcommand{\TN}{\mathbb{N}} \newcommand{\subsets}\[1\]{\mathcal{P}(#1)} \newcommand{\setb}\[1\]{\left\\{#1\right\\}} \newcommand{\land}{\text{ and }} $$

## Algorithms

### Are there cases where existing intuition on O-notation may not hold?

You may find that your existing intuition does not hold when the input-set is something else than a subset of $\TN^d$; say, a subset of $\TR^d$ instead. A cost-function can then be unbounded in a bounded set. However, if you keep modifying the O-notation in terms of the rules given in the cheat-sheet, you'll be fine.

### Why would I use real numbers as inputs to my algorithms?

Hopefully because it is natural to your problem domain. Algorithms are not limited to those which a Turing machine can run. To truly understand what an algorithm is, you need to look at abstract state machines.

### What do you mean "truly understand"?

I'll use an analogy.

Topology (continuous functions, limits, open sets, etc.) can be studied at various levels, starting from $\TR$, to $\TR^d$, to metric spaces and to topological spaces. At each level, the next level of abstraction subsumes the results from the previous level of abstraction *without changing the flavor of the topic*. The definition of a topological space is so simple that it is hard to imagine there being a more generalized structure for studying topology. Although I cannot claim that topological spaces encapsulate the "most abstract" version of topology, the more abstract and simpler the structure, the closer you are to truly understanding topology. That's because then you cannot rely on various other properties that happen to hold in your specific space.

Abstract state machines are to algorithms as topological spaces are to topology. Turing machines (and equivalents) encapsulate only a small subset of all algorithms.

### Why would I be interested in algorithms which can never be implemented on actual computers?

Look at any book on computational geometry (which deals with problems such as finding a convex hull of points, or triangulation of a polygon). Those algorithms are defined in terms of real numbers (a large part of geometry can be said to study subsets of $\TR^d$). While real-world computers do not work with real numbers, it does not make these algorithms useless. They *do* encapsulate practical ideas. It is simply that, by the real number abstraction, you get to concentrate on what is essential, instead of getting bogged down to the details of floating point numbers. While it is an essential problem that the floating point numbers do not work like real numbers, that problem can now be dealt with separately.

Newton's method is also an algorithm under abstract state machines. And it takes as input a differentiable function, which is even more abstract than just real numbers. Want to approximate that algorithm in real-world computers stably using floating point numbers? Welcome to numerical mathematics.

The same thing can be said about matrix decompositions. Here too you want to separate the algorithm of, say, LU-decomposition, from how it can be implemented stably numerically.

## Master theorems

Master theorems are a collection of theorems which provide a shortcut for computing the O-set (or related notation) of a cost-function of certain kinds of recursive algorithms.

### Do Master theorems work for the algorithmic O-notation?

Yes. With the welcome change that you no longer need to care about "regularity" properties, which you may have seen. Things just work.

### Master theorem over integers

Let $a \in \TR^{\geq 1}$, $b \in \TR^{\geq 2}$, $d \in \TR^{\> 0}$, and $F \in R\_{\TN^{\geq 1}}$. A *Master function over integers* is a function $T \in R\_{\TN^{\geq 1}}$ defined by the recurrence equation

$$ T(n) = \begin{cases} a T(\lceil n/b \rceil) + F(n), & n \geq b, \\ d, & n \< b. \end{cases} $$

The set of such functions is denoted by $M\_I(a, b, d, F)$.

Theorem

Let $T \in M\_I(a, b, d, F)$, and $F \in O\_{\TN^{\geq 1}}(n^c)$, where $c \in R^{\geq 0}$. Then

$$ \begin{aligned} \log\_b(a) \< c & \implies T \in O\_{\TN^{\geq 1}}(n^c), \\ \log\_b(a) = c & \implies T \in O\_{\TN^{\geq 1}}(n^c \log\_b(bn)), \\ \log\_b(a) \> c & \implies T \in O\_{\TN^{\geq 1}}(n^{\log\_b(a)}). \end{aligned} $$

If $F \in \Theta\_{\TN^{\geq 1}}(n^c)$, then each $O\_{\TN^{\geq 1}}$ can be replaced with $\Theta\_{\TN^{\geq 1}}$.

### Master theorem over reals

Let $a \in \TR^{\geq 1}$, $b \in \TR^{\> 1}$, $d \in \TR^{\> 0}$, and $f \in R\_{\TR^{\geq 1}}$. A *Master function over reals* is a function $t \in R\_{\TR^{\geq 1}}$ defined by the recurrence equation

$$ t(x) = \begin{cases} a t(x / b) + f(x), & x \geq b, \\ d, & x \< b. \end{cases} $$

The set of such functions is denoted by $M\_R(a, b, d, f)$.

Theorem

Let $T \in M\_R(a, b, d, f)$, and $f \in O\_{\TR^{\geq 1}}(x^c)$, where $c \in \TR^{\geq 0}$. Then

$$ \begin{aligned} \log\_b(a) \< c & \implies t \in O\_{\TR^{\geq 1}}(x^c), \\ \log\_b(a) = c & \implies t \in O\_{\TR^{\geq 1}}(x^c \log\_b(bx)), \\ \log\_b(a) \> c & \implies t \in O\_{\TR^{\geq 1}}(x^{\log\_b(a)}). \end{aligned} $$

If $F \in \Theta\_{\TR^{\geq 1}}(x^c)$, then each $O\_{\TR^{\geq 1}}$ can be replaced with $\Theta\_{\TR^{\geq 1}}$.

## Local linear dominance

### What is a filter basis?

A *filter basis* in a set $X$ is set of subsets $\mathcal{F} \subset \subsets{X}$ such that for each $A, B \in \mathcal{F}$ there exists $C \in \mathcal{F}$ such that $C \subset A \cap B$. A filter basis is the smallest amount of information you need to be able to make sense of limits, or more generally of limit inferior and limit superior. Let $f \in R\_X$. Then

$$\limsup\_{\mathcal{F}} f = \inf \setb{\sup f(A) : A \in \mathcal{F}},$$

$$\liminf\_{\mathcal{F}} f = \sup \setb{\inf f(A) : A \in \mathcal{F}}.$$

Note that $\liminf$ and $\limsup$ always exist as numbers in $\TR^{\geq 0} \cup \setb{\infty}$, since $\inf$ and $\sup$ do by the completeness of $\TR^{\geq 0} \cup \setb{\infty}$. This is in contrast to the concept of a limit $\lim$, which is the number that is equal to both $\liminf$ and $\limsup$. Because of this conditional existence, limits are less useful for the current discussion.

### What is local linear dominance?

Let $\mathcal{F}(X) \subset \subsets{X}$ be a filter basis for each set $X$. Suppose further that these filter bases are related by

$$\mathcal{F}(X') = \setb{F \cap X' : F \in \mathcal{F}}$$

for each $X' \subset X$. Then *$\mathcal{F}$-local linear dominance* is given by

$$O\_X^{\mathcal{F}}(f) = \setb{g \in R\_X : \exists c \in \TR^{\> 0}, A \in \mathcal{F}(X) : (g|A) \leq c (f|A) }.$$

Local linear dominance has the same related notations as linear dominance, defined analogously.

### How is linear dominance related to local linear dominance?

Linear dominance is $\mathcal{F}$-local linear dominance when $\mathcal{F}(X) = \setb{X}$ for each set $X$.

### Limit forms

Local linear dominance can also be given in the following limit form. Let

$$ \begin{aligned} F & = \setb{x \in X : f(x) \> 0}, \\ G & = \setb{x \in X : g(x) \> 0}. \end{aligned} $$

Then

$$ \begin{aligned} f \in O^{\mathcal{F}}\_X(g) & \iff \limsup\_{\mathcal{F}(F)} \frac{f|F}{g|F} \< \infty, \\ f \in o^{\mathcal{F}}\_X(g) & \iff \limsup\_{\mathcal{F}(F)} \frac{f|F}{g|F} \< \infty \land \liminf\_{\mathcal{F}(G)} \frac{f|G}{g|G} = 0, \\ f \in \Omega^{\mathcal{F}}\_X(g) & \iff \liminf\_{\mathcal{F}(G)} \frac{f|G}{g|G} \> 0, \\ f \in \omega^{\mathcal{F}}\_X(g) & \iff \liminf\_{\mathcal{F}(G)} \frac{f|G}{g|G} \> 0 \land \limsup\_{\mathcal{F}(F)} \frac{f|F}{g|F} = \infty, \\ f \in \Theta^{\mathcal{F}}\_X(g) & \iff \limsup\_{\mathcal{F}(F)} \frac{f|F}{g|F} \< \infty \land \liminf\_{\mathcal{F}(G)} \frac{f|G}{g|G} \> 0. \end{aligned} $$

For linear dominance, limit inferior and limit superior reduce to infimum and supremum, respectively. This explains the name of the limit form we used previously for linear dominance.

### Definitions of $o$ and $\omega$ do not look familiar?

This sufficient condition for $o$ might look more familiar:

$$ \begin{aligned} {} & \forall c \in \TR^{\>0}: \exists A \in \mathcal{F}(X): (f|A) \leq c(g|A) \\ \iff & \limsup\_{\mathcal{F}(F)} \frac{f|F}{g|F} = 0 \\ \implies & f \in o^{\mathcal{F}}\_X(g). \end{aligned} $$

Similarly for $\omega$:

$$ \begin{aligned} {} & \forall c \in \TR^{\>0}: \exists A \in \mathcal{F}(X): (g|A) \leq c(f|A) \\ \iff & \liminf\_{\mathcal{F}(G)} \frac{f|G}{g|G} = \infty \\ \implies & f \in \omega^{\mathcal{F}}\_X(g). \end{aligned} $$

The $o^{\mathcal{F}}$ and $\omega^{\mathcal{F}}$ notations (in $X = \TN$) have been defined in books and courses this way, however, as definitions they are incorrect in the sense that they do not quite represent the strict versions of $O^{\mathcal{F}}$ and $\Omega^{\mathcal{F}}$.

### Can I use local linear dominance to analyze algorithms?

**No**; simply because if I say anything else I'll be interpreted incorrectly. At any time during your analysis, you are to remain in the realms of the algorithmic $O$-notation.

After that disclaimer, a careful yes. Some versions of local linear dominance, under suitable conditions, imply linear dominance. In particular, this is the case when the cost-functions are **positive** and the filter-sets are **cofinite**. After checking that such conditions hold, you may use local linear dominance (e.g. limit forms) to deduce containment in linear dominance $O$-set. Note the difference in mind-set; local linear dominances are tools which you may or may not be able to apply in your specific case, and those tools are only meant to help you deduce containment of a function $g \in R\_X$ in $O\_X(f)$, not to be used in analysis themselves.

### Can you give an example of that?

Particularly interesting for this discussion is the filter basis

$$\mathcal{F}(X) = \setb{X \setminus X^{\< n} : n \in \TN},$$

whenever $X \subset \TN^d$ for some $d \in \TN$. In the thesis, I call the corresponding local linear dominance *coasymptotic* (although I'm not too happy about that name). The sets in these filter bases are cofinite. Especially the case $d = 1$ should look familiar; then $X \setminus X^{\< n} = X^{\geq n}$.

Let $f \in R\_{\TN^{\>0}}$ be such that

$$f(n) = n^2 \lvert\sin(n)\rvert + n + 3.$$

Since $f \> 0$, and

$$\limsup\_{\mathcal{F}(\TN^{\>0})} \frac{f(n)}{n^2} = 1 \< \infty,$$

we have that $f \in O\_{\TN^{\>0}}^{\mathcal{F}}(n^2)$. Since the filter-sets are **cofinite** and $n^2 \> 0$, we have that $f \in O\_{\TN^{\>0}}(n^2)$. The potential payoff here was that we got to compute the limit rather than finding a suitable $c \in \TR^{\>0}$ for linear dominance. Here we used local linear dominance as a tool to deduce $f \in O\_{\TN^{\>0}}(n^2)$.

### How would you have done that directly?

Perhaps like this:

$$n^2 \lvert\sin(n)\rvert + n + 3 \leq n^2 + n^2 + 3n^2 = 5n^2.$$

Well, not particularly hard either. Perhaps someone could find an example where finding $c$ is hard but computing the limit is easy?

### Why did you study local linear dominance?

Three reasons.

First, in analogue to software development, they were my unit tests. If linear dominance really is the only suitable algorithmic O-notation, then any other candidate should fail in some way. I wanted to see exactly which properties each definition failed.

Second, as already discussed, they can sometimes by used as tool to deduce containment in an $O$-set.

Third, some of them are needed to show the minimality of the property-set I gave above.

### Anything else about local linear dominance?

Local linear dominance can be generalized to cost-functions which are *eventually non-negative*, meaning $f : X \to \TR$ for which there exists $A \in \mathcal{F}(X)$ such that $f\\|A \geq 0$. In the case of linear dominance, eventually non-negative functions are exactly the cost-functions (which are non-negative), so this generalization does not bring us anything new.

## Multivariate notation

### It seems we now also have a multivariate algorithmic O-notation?

If by multivariate you mean an algoritmic O-notation on the domain $\TN^d$, then yes, O-notation is also defined on that set, as it is in any set.

### But I read a paper which proves that there cannot exist a multivariate algorithmic O-notation?

You are referring to

The content in that paper is fine, but its conclusion is incorrect. The abstract properties of O-notation given in that paper, together with scale-invariance, are in fact equivalent to asymptotic linear dominance (local linear dominance on $\TN^d$ where the filter-sets are of the form $x \geq n$). Hence, the paper only shows that *asymptotic linear dominance* is not suitable as an algorithmic O-notation, not that there cannot be any suitable definition of an algoritmic O-notation.

## Algorithmic O-notation revisited

The O-notation is actually a bit more general than how I defined it at the beginning. Some people use expressions such as $2^{O\_{\TN}(n)}$, and we need to resolve what that means.

### How is the algorithmic O-notation *really* defined?

The *algorithmic O-notation* is the proper class of functions

$$O = \setb{O\_X : P(R\_X) \to \subsets{R\_X} : X \text{ is a set}},$$

where

$$O\_X(F) = \setb{g \in R\_X : \exists f \in F, c \in \TR^{\> 0} : g \leq c f}.$$

The difference is that, in all its generality, the set-specific O-notation $O\_X$ takes in a *set* of functions $F \subset R\_X$, and returns all functions $g \in R\_X$ which are linearly dominated by at least one function $f \in F$. In the terminology of preorders, an O-set $O\_X(F)$ is a down-set of the underlying preorder. In terms of the principal down-sets,

$$O\_X(F) = \bigcup \setb{O\_X(\setb{f}) : f \in F}.$$

If we introduce the abuse of notation $O\_X(f) = O\_X(\setb{f})$ for $f \in R\_X$, then you'll see that before this section we studied an important special case of the O-notation.

### So what does $2^{O\_{\TN}(n)}$ mean?

Literally taken,

$$2^{O\_{\TN}(n)} = \setb{2^f : f \in O\_{\TN(n)}}.$$

However, when written in research papers, it is an abuse of notation for $O\_{\TN}(2^{O\_{\TN}(n)})$. The convention is: if there is an expression which contains O-notation, then the whole-thing is to be wrapped in O-notation. Similarly for the related notations.

To avoid ambiguity, I think it is be better to wrap these kinds of expressions inside explicit O-notations instead (or whatever notation is needed).

### What does $\Omega\_{\TN}(n)^{O\_{\TN}(n)}$ mean?

Literally taken, the function-set

$$\setb{f^g : f \in \Omega\_{\TN}(n) \land g \in O\_{\TN}(n)}.$$

In contrast to the previous example, this time there is no reinterpretation as an O-set or $\Omega$-set based on convention, because the expression uses two different types of notations.

### But $O\_{\TN}(\Omega\_{\TN}(n)^{O\_{\TN}(n)})$ is unambiguous, right?

Yes.

### Cheat-sheet revisited

Using our new understanding of O-notation, we are now able to prove new properties for our cheat-sheet:

$$ \begin{aligned} & \text{Property} && \text{Definition} \\ & \text{ } && \text{ } \\ & \text{Idempotence} && O(O(f)) = O(f), \\ & \text{Composability} && O(O(f) \circ s) = O(f \circ s). \end{aligned} $$

In addition, the cheat-sheet can be in the most part be generalized simply by replacing $f, g, h \in R\_X$ with $F, G, H \subset R\_X$, and $\in$ with $\subset$. Left as an exercise.
> 10 votes

---
Tags: terminology, asymptotics, mathematical-analysis, landau-notation
---


# Question
Title: Maximizing integer sets intersection (with integer delta)
There are two sets of integers with different numbers of items in them.

```
X= { x_0, x_1, ... x_n }, x_0 < x_1 < ... < x_n
Y= { y_0, y_1, ... y_m }, y_0 < y_1 < ... < y_m

```

And there is a function of a single integer defined as

```
F(delta) = CountOfItems( Intersection( X, { y_0+delta, y_1+delta, ... y_m+delta) ) )

```

That is - i add `delta` integer to every element of the `Y` and then count how many same integers are in the `X` and the modified `Y`.

And then the problem - find `delta` that maximizes `F(delta)`.

```
max( F(delta) ), where delta is integer

```

Is there some "mathematical" name for such task and optimal algorithm for this? Obviously i can use brute-force here and enumerate all possible combination - but it does not work for big n and m.

# Answer
> 2 votes
You can compute the sumset (well, difference set) $X-Y$ using standard techniques (Computing Cardinality of Sumsets using Convolutions and FFT).

As an optimization, I suggest first replacing $X,Y$ with $X'=X \bmod p$, $Y'=Y \bmod p$ where $p$ is at least $n+m$ or so. Then, enumerating through the elements of the multiset $X'-Y'$ by decreasing cardinality will give you good candidates for $\delta \bmod p$. The running time to compute $X'-Y'$ will be $O((n+m)\log (n+m))$, and if the maximum value of $F(\delta)$ is sufficiently large, I expect you should be able to find the correct value for $\delta$ among the first few candidates.

---
Tags: sets, integers, enumeration
---


# Question
Title: Number of independent parity checks satisfied by a code
I have been studying quantum error correction codes and as background, I am currently studying the theory of classical linear codes. Despite many efforts, I am unable to understand the following excerpt:

**Any given parity check u divides Hamming space exactly in half,into those vectors which satisfy u and those that do not.Therefore,the 2^k vectors of a linear subspace in 2^n Hamming space can satisfy at most n−k linearly independent parity checks.These parity checks together form the parity check matrix H, which is another way to define the linear subspace.**

# Answer
**Any given parity check $u$ divides Hamming space exactly in half, into those vectors which satisfy $u$ and those that do not.**

Suppose your Hamming space is $X = \\{0,1\\}^n$. A non-zero parity check $u$ divides $X$ into two sets: $X\_0 = \\{ x \in X \mid \langle x,u \rangle = 0 \\}$ and $X\_1 = \\{ x \in X \mid \langle x,u \rangle = 1 \\}$. The two sets have equal size $2^{n-1}$.

Indeed, let $v$ be some non-zero vector such that $\langle u,v \rangle = 1$ (for example, $v$ could contain a single 1 entry, at some index in which $u$ also has a 1 entry). If $x \in X\_0$ then $x + v \in X\_1$, and conversely, if $x \in X\_1$ then $x + v \in X\_0$. Hence we can partition $X$ into pairs $(x,x+v)$ in which the first member is in $X\_0$ and the second in $X\_1$.

Here are two illustrating examples. If $u = (1,\underbrace{0,\ldots,0}\_{n-1\text{ copies}})$ then $X\_0$ consists of all vectors with 0 in the first coordinate, and $X\_1$ consists of all vectors with 1 in the first coordinate. If $u = (\underbrace{1,\ldots,1}\_{n \text{ copies}})$ then $X\_0$ consists of all vectors with even parity, and $X\_1$ consists of all vectors with odd parity.

**Therefore, the $2^k$ vectors of a linear subspace in $2^n$ Hamming space can satisfy at most $n−k$ linearly independent parity checks.** The statement here actually doesn't follow from the preceding statement. However, it is similar in spirit (and a generalization of the preceding statement). Earlier we have considered a single parity check $u$. We showed that if $u$ is non-zero, then the set $\\{x \in X \mid \langle x,u \rangle = 0\\}$ contains exactly half the space. If $u = 0$ then it consists of the entire space.

Now we are considering the common solutions of $m$ different vectors $u\_1,\ldots,u\_m$. The set $C = \\{x \in X \mid \langle x,u\_1 \rangle = \cdots = \langle x,u\_m \rangle = 0\\}$ contains at least $2^{n-m}$ vectors. If the vectors are linearly independent (this generalizes the condition $u \neq 0$), then $C$ contains exactly $2^{n-m}$ vectors. More generally, $C$ contains $2^{n-d}$ vectors, where $d$ is the dimension of the linear span of the vectors $u\_1,\ldots,u\_m$. I won't prove all these statements, but this is basic linear algebra.

If $C$ is a linear subspace containing $2^k$ vectors, and every element $x \in C$ satisfies $\langle x,u\_1 \rangle = \cdots = \langle x,u\_m \rangle = 0$, then the dimension of the span of $u\_1,\ldots,u\_m$ is at most $n-k$, per the discussion above. If we know that $u\_1,\ldots,u\_m$ are linearly independent, then the dimension of their span is $m$, and so $m \leq n-k$.

**These parity checks together form the parity check matrix $H$, which is another way to define the linear subspace.**

We can describe a linear code in two ways. One is using a generator matrix $G$: the linear code consists of all linear combinations of the rows. The other is using a parity check matrix $H$: the code consists of all vectors whose inner product with each row is 0. (Some books use rows, other columns.) Using our earlier notation, the rows of $H$ are just the vectors $u\_1,\ldots,u\_m$, where we insist that the vectors be linearly independent (the same holds for generator matrices).

Here is an example. Let $n = 3$, and consider the code whose generator matrix is $$ \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix} $$ (We note that the same code has many generator matrices, and many parity check matrices.)

The code consists of all linear combinations of the rows: $$ \begin{matrix} 0 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{matrix} $$ You can check that these are exactly the vectors with even parity. Hence a parity check matrix for this code (in this degenerate case, the *unique* parity check matrix) is $$ \begin{bmatrix} 1 & 1 & 1 \end{bmatrix} $$ We can also treat this as a generator matrix of a code. The resulting code is known as the *dual code* (dual to the code for which this matrix functions as a parity check matrix).
> 1 votes

---
Tags: coding-theory
---


# Question
Title: Regular expression for language that does not accept x string (3 letters, |x|=3)
The language I am interested in is $L=\\{w∈\\{a,b,c\\}^\*| w$ contains "$bac$" but not "$cab$"$\\}$. I am thinking that the result will have the form $L=X\_1X\_2X\_3$, where $X\_1=\\{w∈\\{a,b,c\\}^\*| w$ does not contain "$ca$" at the end nor "$cab$" anywhere$\\}$, $X\_2=$"$bac$" and $X\_3=\\{w∈\\{a,b,c\\}^\*| w$ does not contain "$ab$" at the start nor "$cab$" anywhere$\\}$. What I find difficult to express is that "$cab$" does not appear anywhere in $X\_1, X\_3$ (the situation for "ca" and "ab" is simple because they consist only of 2 letters, we can split $X\_1, X\_3$ so that the "cab" problem remains). I have tried creating a NFA for this purpose but the automata needs to have quite a few loops (thus it is hard to find the regular expression). My question is whether there is a clever way to find the representation of non-existance of "cab", other than counting all the possibilities in the NFA that accepts such strings. If there is no such way, how can I find the regular expression of L from the start?

# Answer
> 1 votes
You can create a complete DFA (with all transitions populated) and then just invert the set of start and end states. In your case, using grammar notation, this accepts all strings with the sequence $cab$:

$$\begin{align\*} S & \rightarrow Q\_0 \\ Q\_0 & \rightarrow a Q\_0\\,|\\,b Q\_0\\,|\\,c Q\_1\\ Q\_1 & \rightarrow a Q\_2\\,|\\,b Q\_0\\,|\\,c Q\_1\\ Q\_2 & \rightarrow a Q\_0\\,|\\,b Q\_3\\,|\\,c Q\_1\\ Q\_3 & \rightarrow a Q\_3\\,|\\,b Q\_3\\,|\\,c Q\_3\\,|\\,\epsilon \end{align\*}$$

So this accepts all strings without the sequence $cab$:

$$\begin{align\*} S & \rightarrow Q\_0 \\ Q\_0 & \rightarrow a Q\_0\\,|\\,b Q\_0\\,|\\,c Q\_1\\,|\\,\epsilon\\ Q\_1 & \rightarrow a Q\_2\\,|\\,b Q\_0\\,|\\,c Q\_1\\,|\\,\epsilon\\ Q\_2 & \rightarrow a Q\_0\\,|\\,b Q\_3\\,|\\,c Q\_1\\,|\\,\epsilon\\ Q\_3 & \rightarrow a Q\_3\\,|\\,b Q\_3\\,|\\,c Q\_3 \end{align\*}$$

Now you just have to convert that into a regular expression. Whether or not that's easier is up to you.

You can also directly construct a DFA which accepts $(a|b|c)^\*bac(a|b|c)^\* \setminus (a|b|c)^\*cab(a|b|c)^\*$ using Brzozowski's method, but that's a bit tricky to do by hand for this example.

# Answer
> 0 votes
Try something like this:

(3 character stuff that is allowed many times)\* (1 and 2 character stuff that is allowed once)(bac)(3 character stuff that is allowed many times)\* (1 and 2 character stuff that is allowed once)

The 3 character stuff and 1/2 character stuff are there to forbid the sequence "cab"

# Answer
> 0 votes
This would be the DFA for this problem:

>

Then we can create the Regular Expression from the DFA above:

> $(\[ab\]^\*(c\[bc\]|(ca)^+(a|c\[bc\]))^\*)^\*(ca|c)^\*$

---
Tags: regular-languages, finite-automata, regular-expressions
---


# Question
Title: Walk around a coordinate in circular order to a distance of N
For my development purpose, I need to work on all the 2D coordinates (in whole number) around \[0,0\] from 0 to N distance. For example, with N=1, I need

```
N0: [0, 0]
N1: [-1, -1] [0, -1] [1, -1] [1, 0] [1, 1] [0, 1] [-1, 1] [-1, 0]

```

The order is important. I want to walk these values in a circular way, starting from 0, incrementing the distance each round.

I first created two for-loops, from -N to N on each axes, but the resulting order is the one as you read a book: from top left to bottom right.

Here's the order I aim (the first coordinate to walk on each circle is not important):

Here's a first algorithm I tried, in pseudo code

```
int totalSize = (2*N+1, 2)*(2*N+1, 2)
Vector2[] coordinates = new Vector2[totalSize]
int index = 0
coordinates[index++] = new Vector2(0, 0)
for (int d = 1; d <= N; d++) {
    for (int x = -d; x <= d; x++) {
        coordinates[index++] = new Vector2(x, -d)
        coordinates[index++] = new Vector2(x, d)
    }
    for (int y = -d+1; y <= d-1; y++) {
        coordinates[index++] = new Vector2(-d, y)
        coordinates[index++] = new Vector2(d, y)
    }
}
for (int i=0; i<coordinates.Length; i++) {
    print(coordinates[i])
}

```

But:

* It seems too cumbersome. I don't like the creation of a scructure that retains the coordinates. And 4 for-loops seems not optimized.
* The order of the circles is ok, but the order inside each circle is not the one I described.
* I have the feeling trigonometry can help me, but I can't see how to implement it on discrete values

Any idea?

# Answer
> 1 votes
You can do this in a stateless manner.

Here is python code that generates the infinite walk:

```
def circular():
    yield (0,0)
    x,y = -1,0
    while True:
        yield (x,y)
        if x < 0 and 0 <= y < -x:
            y += 1
        elif y > 0 and x < y:
            x += 1
        elif x > 0 and y > -x:
            y -= 1
        elif y < 0 and x > y:
            x -= 1
        elif x < 0 and y < -1:
            y += 1
        elif x < 0 and y == -1:
            x -= 1
            y += 1

```

---
Tags: algorithms
---


# Question
Title: Why substituting the search part in INSERTION SORT doesnt yield a running time of $\Theta(nlgn)$
$$ \Theta - Tight \ asymptotic \ bound $$

If we change lines $5-7$ in Insertion sort

With BINARY-SEARCH(A,p,r,v)

Why don't we get a running time of $\Theta(n\lg n)$ as we go through the array $\Theta(n)$ and then do a binary search $\Theta(\lg n)$?

# Answer
> 2 votes
You still need to shift $O(n)$ elements to make room for the newly inserted element even if you find the correct position in $O(\log n)$.

---
Tags: algorithms, asymptotics, efficiency
---