# Question
Title: Build a balanced binary tree from list in linear time
I couldn't figure this one out. Given an unsorted list, we want to build a balanced binary tree (not a search tree, namely - left child is of lower key, and right child of higher key). Can we do it in linear time? **Thanks!**

# Answer
> 3 votes
Answer #2.

An alternative approach (arguably more elegant). This basically does the same operations as my other answer, just in a different order. It is as follows:

```
build-tree(list A of length n):
  if n == 1:
    return singleton tree of the 1 element in A.

  let m be the median element of A  # linear time select

  let L be all elements in A less than m
  let R be all elements in A greater than m

  construct a max-heap HL from L in linear time
  construct a min-heap HR from R in linear time

  let m be the root node of tree T
  let the structure of HL be the structure of all  left-children in T
  let the structure of HR be the structure of all right-children in T

  return T

```

Let's try an example on $\[8,12,9,15,5,1,10,3,11,14,2,4,13,7,6\]$.

1. First we find the median $m = 8$.
2. We find $L = \[5,1,3,2,4,7,6\]$ and $R = \[12,9,15,10,11,14,13\]$.
3. Then we have max heap `HL` as shown below:

4. Then we have min heap `HR` as shown below:

5. Then we fill in the structure of `T` as follows:

The dotted lines represent the underlying structure of each original heap.

---

### Analysis

The running time is as follows:

* $O(n)$ for finding the median.
* $O(n)$ for constructing the two heaps.
* $O(n)$ for merging the two heaps.

Thus, the total time is still $O(n)$.

# Answer
> 1 votes
We can do this similar to the linear construction of a heap.

We will start with the leaves. We need to determine what elements will be left child leaves and which will be right child leaves.

Assume w.l.o.g. that $n = 2^k - 1$. There will be $2^{k-1}$ leaves where $2^{k-2}$ will be left children, and the other $2^{k-2}$ will be right children.

Since we know every left child must be less than it's parent, we can guarantee this by using the smallest $2^{k-2}$ elements for left child leaves. Similarly we use the largest $2^{k-2}$ elements for right child leaves. The recursive procedure is as follows (building from the leaves to the root).

```
build-tree(list A of length n):
  if n == 1:
    return singleton tree of the 1 element in A.

  let n = 2^k - 1
  let l = 2^(k-2)         # rank of  left partition element
  let r = n - 2^(k-2) + 1 # rank of right partition element

  l_elem = SELECT(l, A)   # linear time select
  r_elem = SELECT(r, A)   # linear time select

  let L be all elements in A <= l_elem
  let R be all elements in A >= r_elem
  let C be all elements in A that are not in L or R

  let tree T = build-tree(C)

  for i in {0 ... l}:
    let L[i] be the  left child of leaf i in T
    let R[i] be the right child of leaf i in T

  return T

```

Let's try an example on $\[8,12,9,15,5,1,10,3,11,14,2,4,13,7,6\]$. The `L`, `R`, and `C`s would be as follows:

1. $L = \[1, 3, 2, 4\]$, $C = \[8, 9, 5, 10, 11, 7, 6\]$, $R = \[12, 15, 14, 13\]$
2. $L = \[5, 6\]$, $C = \[8, 9, 7\]$, $R = \[10, 11\]$
3. $L = \[7\]$, $C = \[8\]$, $R = \[9\]$
4. return `TreeNode(8)`.

Then it would recursively build the following tree:

---

### Analysis

We get the following recurrence:

$$T(2^k - 1) = T(2^{k-1} - 1) + O(n)$$

This comes out to be $O(n)$.

---
Tags: data-structures, binary-trees
---


# Question
Title: Solving recurrence equation $T(n)=T(n^{2/3})+17$
How can the following recurrence equation be solved by one of three main ways:

$$T(n)=T(n^{2/3})+17$$

I have tried solving it by the iteration way. However it does not work for me since I can't find the equation with $i$, i.e the generic equation.

# Answer
> 1 votes
We can do this pretty easily with a change of variables here. Let $n = 2^{(3/2)^k}$ we then can rewrite $T(n)$ as: $$S(k) = S(k - 1) + 17$$ We have $S(k) = O(k)$. Then converting $k$ back to $n$ we have: $$k = \log\_{3/2} \log\_2 n$$ Thus, $T(n) = O(\log \log n)$.

# Answer
> 3 votes
This post answers the original version of the question, where the recurrence relation is

$$T(n)=T\left(\frac{n^2}{3}\right)+17$$

---

The recurrence relation is somewhat unconventional. Here is an outline to solve it.

Suppose $n\ge 6$. Let $n=3\cdot2^{2^{m}}$, where $m=\log\_2(\log\_2\frac n3)\ge0$.

$$\begin{align} T(n) &=T\left(3\cdot2^{2^{m}}\right) =T\left(\sqrt{3\cdot\left(3\cdot2^{2^{m}}\right)}\right)-17\\ &=T\left(3\cdot2^{2^{m-1}}\right)-17 =T\left(\sqrt{3\cdot3\left(\cdot2^{2^{m-1}}\right)}\right)-2\cdot17\\ &=T\left(3\cdot2^{2^{m-2}}\right)-2\cdot17 =T\left(\sqrt{3\cdot\left(3\cdot2^{2^{m-2}}\right)}\right)-3\cdot17\\ &=\cdots\\ &=T\left(3\cdot2^{2^{m-\lceil m\rceil}}\ \right)-\lceil m \rceil\cdot 17 \end{align}$$

Since $-1\lt m-\lceil m\rceil\le0$, $3\sqrt2\lt3\cdot2^{2^{m-\lceil m\rceil}}\le6.$ So $T(n)\sim -17\log\_2(\log\_2 n)$ when $n$ goes to $\infty$.

---

Here are two related exercises.

**Exercise 1**. What is the recurrence relation for function $S$ such that $S(n)=T(3n)$?

**Exercise 2**. What is the asymptotic behavior of $T(n)$ if $n$ goes to 3 from above, assuming $T$ is continuous?

# Answer
> 1 votes
Another similar answer to Apass.Jack on the "original" question.

First flip the function around:

$$T\left(\frac{n^2}{3}\right) = T(n) - 17$$

Convert it to an intelligible form by a change of variables where $m = \tfrac{n^2}{3}$:

$$T(m) = T(\sqrt{3m}) - 17$$

Try another change of variables where $m = 3 \cdot 2^{2^\omega}$. We get:

$$T(\omega) = T(\omega - 1) - 17$$

Thus $T(\omega) = -17\omega$. Now we work backwards:

$$\begin{align\*} T(\omega) & = -17 \omega\\ T(m) & = -17 \log\_2 \log\_2 (m / 3)\\ T(n^2 / 3) & = -17 \log\_2 \log\_2 (n^2 / 9)\\ T(n) & = -17 \log\_2 \log\_2 (n / 3)\\ \end{align\*}$$

This assumes a base case of $T(\omega = 1) = -17$ or the following other assumed base cases:

$$\begin{align\*} T(\omega = 1) &= -17\\ T(m = 6) & = -17\\ T(n = 6) & = -17 \end{align\*}$$

---
Tags: recurrence-relation
---


title: Find a point shared by maximum segments

text:
# Question
Title: Find a point shared by maximum segments
Given: $N$ segments (arrays) of ordered integers, integers could be from $-K$ to $K$.

Example:

```
Segment 1: [-2,-1,0,1,2,3]
Segment 2: [1,2,3,4,5]
Segment 3: [-3,-2,-1,0,1]

```

You can represent them as \[min, max\]---it is equivalent:

```
Segment 1: [-2,3]
Segment 2: [1,5]
Segment 3: [-3,1]

```

How can I find an integer that belongs to the maximum amount of segments? For the given example, it is 1.

I look for the most efficient algorithm.

# Answer
Let's use $+$ to denote the start of a segment and $-$ to denote the end. For each segment, create two pairs, one for each endpoint:

```
Segment1: (-2, +), (3, -)
Segment2: (1, +), (5, -)
Segment3: (-3, +), (1, -)

```

Sort the $2N$ pairs by their first coordinate (in case of equality, put + before -). You can do this in time $O(N \log N)$ with any reasonable sorting algorithm, or in time $O(N + K)$ using key-indexed counting. In the example, we get:

```
(-3, +)
(-2, +)
(1, +)
(1, -)
(3, -)
(5, -)

```

Now process the endpoints in order. Maintain a count of the number of active segments, which is initially 0. Every time you process a $+$, increase the count by 1. Every time you process a $-$, decrease the count by 1. After processing each endpoint, check if the new count is higher than the largest count so far; if it is, update your solution.

```
(-3, +) -> count=1, max_count=0, sol=-3
(-2, +) -> count=2, max_count=1, sol=-2
(1, +) -> count=3, max_count=2, sol=1
(1, -) -> count=2, max_count=3, sol=1
(3, -) -> count=1, max_count=3, sol=1
(5, -) -> count=0, max_count=3, sol=1

```

This second phase of the algorithm takes time proportional $N$. The whole algorithm takes time $O(N \log N)$ with a generic sort, or $O(N + K)$ with key-indexed counting.
> 11 votes

# Answer
Let's build an array of size **2\*k+1** all initialized with 0. For each segment of the form \[L, R\], we will add 1 at **Lth** index and subtract 1 from **R+1th** index.

```
Note : We add K to every values to shift the range from -K to +K to 0 to 2*K.

```

Now to obtain the result, we will perform a prefix sum.

```
array[i] = array[i-1] + array[i], where 1 <= i <= 2*K ( assuming 0-based indexing)

```

Let **i** be the index with maximum value. Then answer will be **i-K**.
Let us solve the asked example :

```
Let K = 5 and segments are [-2, 3], [1, 5] and [-3, 1]. Then after adding K the segments become
[3, 8], [6, 10] and [2, 6].
On performing the +1 and -1 updates our array will be
[0, 0, 1, 1, 0, 0, 1, -1, 0, -1, 0, -1].
Prefix sum will result into
[0, 0, 1, 2, 2, 2, 3, 2, 2, 1, 1, 0].
Hence the index with max value is 6 and hence answer will be 6 - 5 = 1.

```

Time complexity of above approach will be **O(max(N, K))**.
> 1 votes

---
Tags: algorithms, time-complexity, arrays
---


# Question
Title: Devising a way to spot a contradiction given a set of statements using graphs
If we had statements like: John is as tall as Mark, Mark is as tall as Sally, Chuck is as tall as Sally, Chuck is shorter than John.

Would there be a way to figure out that there is a contradiction in this set of statements using graphs?

My attempt at it was to symbolize each of the names, assuming they have different first letters to statements like, J = M, M = S, C = S, C ≠ J.

My idea is to find a cycle after using DFS on some graph but I'm having trouble making the actual graph which is perhaps the most troublesome part.

I hope I'm on the right track. Any help would be much appreciated!

Edit: The comment makes a good point and the statements do have inequalities as well, but I'd like to make another attempt at that on my own afterwards. If the question were to be simplified to just "as tall" and "not as tall", what sort of graph would I make?

# Answer
> 1 votes
First, you can consider only the equality relationships and build an undirected graph with each edge representing each equality relationship. Then you can simply apply BFS or DFS to partition this graph into connected components.

Next you can consider the "\<" and "\>" relationships. You can treat each connected component as a vertex and add directed edges so that $(u,v)$ represents the relationship $u\<v$. Then you can detect if there is a cycle in the directed graph by DFS again. If there is cycle, there is a contradiction among these relationships; otherwise the relationships we processed so far are consistent.

At last you can consider the "$\neq$" relationships. You can simply check for each relationship $a\neq b$ if $a$ and $b$ belong to the same connected component. If $a$ and $b$ belong to different connected components for all relationships $a\neq b$, then all the relationships are consistent; otherwise there is a contradiction.

---
Tags: algorithms, graphs, graph-traversal
---


title: Minimum diameter spanning tree problem

text:
# Question
Title: Minimum diameter spanning tree problem
Minimum diameter spanning tree (MDST) problem is defined as following: given the connected weighted graph $G(V, E)$, weight function $w: E \rightarrow R, w(e) \> 0\ \forall e \in E$, find the spanning tree $T(V, E')$ of $G$ such as maximal distance between vertices in $T$ is minimal.

I've done my research and haven't found much literature on this particular problem (I've seen Euclidean MDST and bounded MDST, but not MDST itself) and wondered if there's any good explanation of polynomial solution to that problem. Also, I saw a theorem stating that $\Theta(n^3)$ solution exists here, but no full solution is anywhere.

I believe this community would benefit if solution is described here.

# Answer
The answer is given in the paper that you link to. Specifically, there is a $O(mn+n^2 \log n)$-time algorithm for the problem (with positive edge weights, as required) that works as follows.

The *absolute 1-center* is the point in the graph - either a vertex or an edge - from which the distance to the furthest vertex is minimum. Now, denote by $T(v)$ a shortest path tree connecting $v$ to all vertices in $V$. It holds that $T(a)$ is a minimum diameter spanning tree of $G$, where $a$ is an absolute 1-center of $G$. Here, if the absolute 1-center is an *edge*, we subdivide it to obtain the vertex $a$ from which $T(a)$ is then computed from.

An absolute 1-center $a$ can be found by the Kariv-Hakimi algorithm within the mentioned bound, while $T(a)$ is computed by any standard shortest path algorithm.
> 7 votes

---
Tags: graphs, polynomial-time, minimum-spanning-tree
---


# Question
Title: NP-Completeness and commutative property
If $X$ is NP-complete and for some $Y, X\leq\_p Y$ and $Y\leq\_p X$ what can we say about $Y$?

My intuition says that this is only the case when $X=Y$ but I'm not sure how to justify this.

# Answer
> 2 votes
Your property holds for, for example 3-SAT and 3-COLOURABILITY so it's certainly not required that $X=Y$.

The fact that $Y\leq\_p X$ and $X\in\mathrm{NP}$ tells you that $Y\in\mathrm{NP}$; the fact that $X$ is $\mathrm{NP}$-complete and $X\leq\_p Y$ tells you that $Y$ is $\mathrm{NP}$-hard. Therefore, $Y$ is $\mathrm{NP}$-complete.

# Answer
> 2 votes
Since $X$ is NPC and reduces in polynomial time to $Y$, we have that $Y$ is also NPC as nicely explained in David's answer. Further, since $Y$ is also reducible in polynomial time to $X$, we say that $X$ and $Y$ are *polynomially equivalent*.

It is not at all true that $X$ would have to equal $Y$ in order for $X$ and $Y$ to be polynomially equivalent. You can find a good amount of examples from e.g., graph theory by just searching with this term.

---
Tags: complexity-theory, np-complete, reductions
---


# Question
Title: Using Union find to check whether there is a cycle in a graph
I'm trying to learn about DSU, and I came across a point stating if two vertices belong to the same sub-set, then a cycle exists. In terms of implementation of DSU, I'm unable to make sense of this. Could you share a proof or explain this?

# Answer
> 4 votes
The way it works is that your sets are connected components of the graph. You build such components incrementally, adding one edge at a time. When you add each edge, you ask if the vertices are part of the same component, if so then you have a cycle, if not, then you join the two components (perform a set union). Keep adding edges until you run out of them or found a cycle.

If we look at the definition of connected component, it implies that for each two vertices $u$ and $v$ in the same component, there's a path connecting them.

The algorithm works as follows: you start adding a Singleton set for each vertex to your dsu. These are your first components. Then add the first edge, obviously, the two vertices will be on separate sets (components), and you just found an edge connecting them, so that means they belong to the same component. So you join the two sets (components) into a single one, as your edge is the path connecting them.

You keep going, everytime you find an edge connecting two vertices in different components, you can join the components, as that edge will be a bridge connecting them: if the vertices are $u$ and $v$, and you have $w$ in $u$'s component, you can assert that there's a path from $w$ to $v$ passing through your current edge. Is easy to see now that all vertices in both components are now connecting. So join the two sets (components) in one.

Finally, when you process an edge which vertices $u, v$ are on the same component, you just found a cycle: since both are on the same component, you know there's a path between them, and your new edge happens to close the cycle.

DSU is typically used for implementing Kruskal's algorithm, and uses the same properties. You can do a quick Google search for Kruskal with DSU, for examples.

---
Tags: data-structures, union-find
---


# Question
Title: Solving or approximating recurrence relations for sequences of numbers
In computer science, we have often have to solve recurrence relations, that is find a **closed form** for a recursively defined sequence of numbers. When considering runtimes, we are often interested mainly in the sequence's **asymptotic** growth.

Examples are

1. The runtime of a tail-recursive function stepping downwards to $0$ from $n$ whose body takes time $f(n)$:

$\qquad \begin{align} T(0) &= 0 \\ T(n+1) &= T(n) + f(n) \end{align}$
2. The Fibonacci sequence:

$\qquad \begin{align} F\_0 &= 0 \\ F\_1 &= 1 \\ F\_{n+2} &= F\_n + F\_{n+1} \end{align}$
3. The number of Dyck words with $n$ parenthesis pairs:

$\qquad\begin{align} C\_0 &= 1 \\ C\_{n+1}&=\sum\_{i=0}^{n}C\_i\\,C\_{n-i} \end{align}$
4. The mergesort runtime recurrence on lists of length $n$:

$\qquad \begin{align} T(1) &= T(0) = 0 \\ T(n) &= T(\lfloor n/2\rfloor) + T(\lceil n/2\rceil) + n-1 \end{align}$

What are methods to solve recurrence relations? We are looking for

* general methods and
* methods for a significant subclass

as well as

* methods that yield precise solutions and
* methods that provide (bounds on) asymptotic growth.

This is supposed to become a reference question. Please post one answer per method and provide a general description as well as an illustrative example.

# Answer
## Converting Full History to Limited History

This is a first step in solving recurrences where the value at any integer depends on the values at *all* smaller integers. Consider, for example, the recurrence $$ T(n) = n + \frac{1}{n}\sum\_{k=1}^n \big(T(k-1) + T(n-k)\big) $$ which arises in the analysis of randomized quicksort. (Here, $k$ is the rank of the randomly chosen pivot.) For any integer $n$, the value of $T(n)$ depends on all $T(k)$ with $k\<n$. Recurrences of this form are called *full history* recurrences.

To solve this recurrence, we can transform it into a *limited history* recurrence, where $T(n)$ depends on only a constant number of previous values. But first, it helps to simplify the recurrence a bit, to collect common terms and eliminate pesky fractions. \begin{align\*} n T(n) &= n^2 + 2\sum\_{k=1}^{n-1} T(k) \end{align\*} Now to convert to a limited-history recurrence, we write down the recurrence for $T(n-1)$, subtract, and regather terms: \begin{align\*} (n-1) T(n-1) &= (n-1)^2 + 2\sum\_{k=1}^{n-2} T(k) \\ \implies nT(n) - (n-1)T(n-1) &= (2n-1) + 2T(n-1) \\\\[1ex\] \implies n T(n) &= (2n-1) + (n+1) T(n-1) \\\\[1ex\] \implies \frac{T(n)}{n+1} &= \frac{2n-1}{n(n+1)} + \frac{T(n-1)}{n} \end{align\*}

Now if we define $t(n) = T(n)/(n+1)$ and replace the fraction $\frac{2n-1}{n(n+1)}$ with the simpler asymptotic form $\Theta(1/n)$, we obtain the much simpler recurrence $$ t(n) = \Theta(1/n) + t(n-1). $$ Expanding this recurrence into a summation immediately gives us $t(n) = \Theta(H\_n) = \Theta(\log n)$, where $H\_n$ is the $n$th harmonic number. We conclude that $\boldsymbol{T(n) = \Theta(n\log n)}$.
> 35 votes

# Answer
## Generating Functions $\newcommand{\nats}{\mathbb{N}}$

Every series of numbers corresponds to a generating function. It can often be comfortably obtained from a recurrence to have its coefficients -- the series' elements -- plucked.

This answer includes the general ansatz with a complete example, a shortcut for a special case and some notes about using this method to obtain asymptotics (even if the precise result can not be obtained).

### The Method

Let $(a\_n)\_{n\in\nats}$ a series of numbers. Then, the formal power series

$\qquad \displaystyle A(z) = \sum\_{n=0}^\infty a\_nz^n$

is the *ordinary* generating function¹ of $(a\_n)\_{n\in\nats}$. The coefficients in the series expansion of $A(z)$ equal the sequence, i.e. $\[z^n\]A(z) = a\_n$. For example, the ordinary generating function of the famous Catalan numbers $C\_n$ is

$\qquad \displaystyle C(z) = \frac{1 - \sqrt{1 - 4z}}{2z}$.

The definition of $A$ is also our ansatz for solving a recurrence. This works best for linear recurrences, so assume for the sake of simplicity a recurrence of the form

$\qquad \begin{align} a\_0 &= c\_0 \\ &\vdots \\ a\_{k-1} &= c\_{k-1} \\ a\_n &= f(n) + \sum\_{i=1}^k b\_i a\_{n-i} \qquad , n \geq k \end{align}$

for some fixed $b\_1, \dots, b\_k \in \mathbb{R}$ and $f(n) : \nats \to \nats$ a function independent of all $a\_i$. Now we simply insert both anchors and recursive part into the ansatz, that is

$\qquad \begin{align} A(z) &= \sum\_{n=0}^\infty a\_nz^n \\ &= c\_0z^0 + c\_1z^1 + \dots + c\_{k-1}z^{k-1} + \sum\_{n=k}^\infty \left\[ f(n) + \left(\sum\_{i=1}^k b\_i a\_{n-i}\right)\right\] z^n \end{align}$

Using mechanics of sum manipulation, properties of formal power series and known identities², the last right-hand side has to be brought into closed forms, typically in terms of $A(z)$. The resulting equation can (often) be solved for $A(z)$. The series expansion of the result (which may be easily obtained, known or otherwise approachable) is essentially the solution.

Good introductions can be found in Wilf's book \[3\] and in GKP \[4\]. Advanced material has been collected by Flajolet and Sedgewick \[5\].

### Example

Consider

$\qquad \begin{align} a\_0 &= 1 \\ a\_1 &= 2 \\ a\_n &= 5n + 3a\_{n-1} - 2a\_{n\_2} \qquad , n \> 1 \end{align}$

We calculate:

$\qquad \begin{align} A(z) &= \sum\_{n=0}^\infty a\_n z^n \\ &= 1 + 2z + \sum\_{n=2}^\infty \left\[ 3a\_{n-1} - 2a\_{n-2} + 5n\right\]z^n \\ &= 1 + 2z + 3\sum\_{n=2}^\infty a\_{n-1}z^n - 2\sum\_{n=2}^\infty a\_{n-2}z^n + 5\sum\_{n=2}^\infty n z^n \\ &= 1 + 2z + 3z\sum\_{n=1}^\infty a\_nz^n - 2z^2\sum\_{n=0}^\infty a\_n z^n + 5\sum\_{n=2}^\infty n z^n \\ &= 1 + 2z + 3z(A(z) - a\_0) - 2z^2A(z) + 5 \left( \frac{z}{(1-z)^2} - z\right) \\ &= 1 - 6z + (3z - 2z^2)A(z) + \frac{5z}{(1-z)^2} \end{align}$

This solves to

$\qquad \begin{align} A(z) &= \frac{1 - 3z + 13z^2 - 6z^3}{(1-2z)(1-z)^3} \\ &= \frac{16}{1-2z} - \frac{5}{1-z} - \frac{5}{(1-z)^2} - \frac{5}{(1-z)^3} \\ &= 16\sum\_{n=0}^\infty 2^n z^n - 5\sum\_{n=0}^\infty z^n - 5 \sum\_{n=0}^\infty (n+1) z^n - 5\sum\_{n=0}^\infty \frac{(n+1)(n+2)}{2} z^n \end{align}$

Now we can finally read off

$\qquad \begin{align} a\_n &= 16 \cdot 2^n - 5 - 5(n+1) - \frac{5}{2}(n+1)(n+2) \\ &= 2^{n+4} - \frac{5}{2}n^2 - \frac{25}{2}n - 15 \end{align}$

Once you get used to it, you notice that this is all quite mechanic. In fact, computer algebra can do all this stuff for you in many cases. The good is that it remains (more or less) that mechanic even if the recurrence is more complex. See here for a more involved, less mechanic example.

Also note that the general techniques also work if the objects sought are complex numbers, or even polynomials.

### A Shortcut

For linear and homogeneous recurrences, i.e. such of the form

$\qquad \begin{align} a\_0 &= c\_0 \\ &\vdots \\ a\_{k-1} &= c\_{k-1} \\ a\_n &= \sum\_{i=1}^k b\_i a\_{n-i} \qquad , n \geq k \end{align}$

the above goes through in exactly the same way, every time. By performing above calculation symbolically, we find the following lemma. Let

$\qquad \displaystyle z^k - b\_1 z^{k-1} - b\_2 z^{k-2} - \dots - b\_k$

be the *characteristic polynomal* (of the recurrence). Let furthermore $\lambda\_1, \dots, \lambda\_l$ the (pairwise distinct) zeros of said polynomial with multiplicity $r\_i$, respectively. Then, the desired coefficient is given by

$\qquad \displaystyle a\_n = \sum\_{i=1}^l \sum\_{j=1}^{r\_i} b\_{i,j} \cdot n^{j-1} \cdot \lambda\_i^n$

with unknown $b\_{i,j}$. As the characteristic polynomial has degree $k$, there are exactly $k$ (complex) zeros, i.e. the $r\_i$ sum to $k$. Therefore, the missing coefficients can be determined by solving the linear equation system with $k$ equations obtained by equating above formula with any $k$ of the $a\_n$ (e.g. the anchors).

### Asymptotics

Getting to a closed form for $A(z)$ is usually the easy part. Expressing it in generating functions we know the coefficiencts of (as we did in the example) quickly becomes hard, though. Examples are $C(z)$ from above and the one for the number of Dyck words mentioned in the question.

One can employ complex analysis machinery, specifically singularity analysis, in order to obtain asymptotics for the coefficients; buzzwords include Darboux's method and saddle-point method. These are based on the residue theorem and Cauchy's integral formula. See \[6\] for details.

---

1. You can do similar things with exponential, Dirichlet and some other generating functions. Which works best depends on the sequence at hand and in particular whether you find the necessary closed forms.
2. For example from the TCS Cheat Sheet or \[3\].
3. generatingfunctionology by H. Wilf (1994, 2nd ed.) -- available for free download
4. Concrete Mathematics by R.L. Graham, D.E. Knuth and O. Patashnik (1994, 2nd ed.)
5. Introduction to the Analysis of Algorithms by R. Sedgewick and P. Flajolet (2nd edition, 2013) -- available for free download
6. Analytic Combinatorics by P. Flajolet and R. Sedgewick (2009) -- available for free download
> 29 votes

# Answer
## Master Theorem

The Master theorem gives asymptotics for the solutions of so-called divide & conquer recurrences, that is such that divide their parameter into proportionate chunks (instead of cutting away constants). They typically occur when analysing (recursive) divide & conquer algorithms, hence the name. The theorem is popular because it is often incredibly easy to apply. On the other hand, it can only be applied to recurrences of the following form:

$\qquad \displaystyle T(n) = a \cdot T\left(\frac{n}{b}\right) + f(n) $

with $a \geq 1, b \> 1$. There are three cases

1. $\quad \displaystyle f \in O\left( n^{\log\_b (a) - \varepsilon} \right)$

for some $\varepsilon \> 0$;
2. $\quad \displaystyle f \in \Theta\left( n^{\log\_b a} \log^{k} n \right)$,

for some $k \geq 0$;
3. $\quad \displaystyle f \in \Omega\left( n^{\log\_b (a) + \varepsilon} \right)$

for some $\varepsilon \> 0$ *and*

$\quad \displaystyle a f\left( \frac{n}{b} \right) \le c f(n)$

for some $c \< 1$ and $n \to \infty$.

which imply the asymptotics

1. $T \in \Theta\left( n^{\log\_b a} \right)$,
2. $T \in \Theta\left( n^{\log\_b a} \log^{k+1} n \right)$ and
3. $T \in \Theta \left(f \right)$,

respectively. Note that the base cases are not stated or used here; that makes sense, considering we are only investigating *asymptotic* behaviour. We silently assume that they are some constants (what else can they be. *Which* constants we don't see is irrelevant, they all vanish in the $\Theta$.

### Examples

1. Consider the recurrence

$\qquad \displaystyle T(n) = 4T\left(\frac{n}{3}\right) + n$.

With $f(n) = n, a=4$ and $b=3$ -- note that $\log\_b a \approx 1.26$ we see that case one applies with $\varepsilon = 0.25$. Therefore, $T \in \Theta(n^{\log\_3 4}) = \Theta(n^{1.261\dots})$.
2. Consider the recurrence

$\qquad \displaystyle T(n) = 2T(n/2) + n$.

With $f(n) = n, a=2$ and $b=2$ -- note that $\log\_b a = 1$ we see that case two applies with $k=0$. Therefore, $T \in \Theta(n \log n)$.
3. Consider the recurrence

$\qquad \displaystyle T(n) = 3T\left(\frac{n}{4}\right) + n$.

With $f(n) = n, a=3$ and $b=4$ -- note that $\log\_b a \approx 0.79$ we see that case three applies with $\varepsilon = 0.2$ and $c=1$. Therefore, $T \in \Theta(n)$.
4. Consider the recurrence

$\qquad \displaystyle T(n) = 16T\left(\frac{n}{4}\right) + n!$

Here we have $a = 16$, $b=4$ and $f(n) = n!$ - many standard examples will have polynomial $f$, but this is not a rule. We have $\log\_b a = 2$, and case three applies again. In this instance though, we can choose any $\varepsilon$ and $c \> 0$ as $n! \in \Omega(n^{k})$ for all $k$. Hence $T \in \Theta(n!)$.

### Further reading

* It is well possible that none of the Master theorem's cases applies. For example, the subproblems may not have equal size or have a more complex form. There are some extensions to the Master theorem, for instance Akra-Bazzi \[1\] or Roura \[2\]. There is even a version that works for discrete recurrences (i.e. floors and ceils are used on the recursive parameters) *and* provides sharper results \[3\].
* Usually, you have to massage the actual recurrence relation you have into shape before you can apply the Master theorem. Common transformations that preserve asymptotics include dropping floors and ceils as well as assuming $n=b^k$. Take care not to break things here; refer to \[4\] section 4.6 and this question for details.

---

1. On the Solution of Linear Recurrence Equations by M. Akra and L. Bazzi (1998)
2. An improved master theorem for divide-and-conquer recurrences by S. Roura (1997)
Refers to other improved master theorems.
3. A master theorem for discrete divide and conquer recurrences by M. Drmota and W. Szpankowski (2011)
4. Introduction to Algorithms by Cormen et al. (2009, 3rd edition)
> 20 votes

# Answer
## Guess & Prove

Or how I like to call it, the "$\dots$ technique". It can be applied to all kinds of identities. The idea is simple:

> Guess the solution and prove its correctness.

This is a popular method, arguably because it usually requires some creativity and/or experience (good for showing off) but few mechanics (looks elegant). The art here is to make good, educated guesses; the proof is (in our case) usually a more or less simple induction.

When applied to recurrences, "guessing" is typically done by

* *expanding* the recurrence a couple of times,
* figuring out the *anchor* and
* *guessing the pattern* for the intermediate (the $\dots$).

### Simple Example

$\qquad \begin{align} s\_0 &= s\_1 = s\_2 = 1 \\ s\_n &= 5s\_{n-3} + 6 \qquad\qquad n \geq 2 \end{align}$

Let us expand the definition of $s\_n$ a few times:

$\qquad \begin{align} s\_n &= 5s\_{n-3} + 6 \\ &= 5(5s\_{n-6} + 6) + 6 \\ &= 5(5(5s\_{n-9} + 6) + 6) + 6 \\ &\ \vdots \\ &= \underbrace{5(5(5( \dots 5\cdot 1}\_{n \div 3 \text{ times}} + \underbrace{6 \dots ) + 6) + 6) + 6}\_{n \div 3 \text{ times}} \end{align}$

Here, the pattern is easy to spot and it leads us to the claim:

$\qquad \begin{align} s\_n &= 5^{\left\lfloor\frac{n}{3}\right\rfloor} + 6\cdot \sum\_{i=0}^{\left\lfloor\frac{n}{3}\right\rfloor - 1} 5^i \\ &= \frac{5}{2}\cdot 5^{\left\lfloor\frac{n}{3}\right\rfloor} - \frac{6}{4} \end{align}$

Now we prove the identity by induction. For $n \in \\{0,1,2\\}$, we can establish correctness by a plugging in the respective value. Assuming the identity holds for all $n' \leq n$ for an arbitrary but fixed $n \geq 3$, we calculate

$\qquad \displaystyle \begin{align} s\_{n+3} &= 5s\_n + 6 \\ &= 5\cdot \left( \frac{5}{2}\cdot 5^{\left\lfloor\frac{n}{3}\right\rfloor} - \frac{6}{4} \right) + 6 \\ &= \frac{5}{2}\cdot 5^{\left\lfloor\frac{n}{3}\right\rfloor + 1} - \frac{6}{4} \\ &= \frac{5}{2}\cdot 5^{\left\lfloor\frac{n+3}{3}\right\rfloor} - \frac{6}{4} \end{align}$

which proves the identity by the power of induction.

If you try to use this on more involved recurrences, you quickly encounter the prime disadvantage of this method: it can be hard to *see* the pattern, or condense it to a nice closed form.

### Asymptotics

It is possible to use this method for asymptotics, too. Be aware, though, that you *have to guess the constants* for the Landau symbols as there has to be *one* constant that establishes the bound *for all* $n$, i.e. the constant factor can not change during the induction.

Consider, for example, the Mergesort runtime recurrence, simplified for the case of $n=2^k$¹:

$\qquad \begin{align} T(1) &= T(0) = 0 \\ T(n) &= 2T(n/2) + n-1 \qquad n \geq 1 \end{align}$

We *guess* that $T(n) \in O(n\log n)$ with constant $c=1$, that is $T(n) \leq n\log n$. We prove this by induction over $k$; the inductive step looks like this:

$\qquad \begin{align} T(n) &= 2T(n/2) + n-1 \\ &\leq 2\frac{n}{2}\log \frac{n}{2} + n - 1 \\ &= n\log n - n\log 2 + n - 1 \\ &\lt n \log n \end{align}$

---

1. For non-decreasing sequences of naturals, every infinite subsequence has the same asymptotic growth as the original sequence.
> 17 votes

# Answer
# The Akra-Bazzi method

The Akra-Bazzi method gives asymptotics for recurrences of the form: $$ T(x) = \sum\_{1 \le i \le k} a\_i T(b\_i x + h\_i(x)) + g(x) \quad \text{for $x \ge x\_0$} $$ This covers the usual divide-and-conquer recurrences, but also cases in which the division is unequal. The "fudge terms" $h\_i(x)$ can cater for divisions that don't come out exact, for example. The conditions for applicability are:

* There are enough base cases to get the recurrence going
* The $a\_i$ and $b\_i$ are all constants
* For all $i$, $a\_i \> 0$
* For all $i$, $0 \< b\_i \< 1$
* $\lvert g(x) \rvert = O(x^c)$ for some constant $c$ as $x \rightarrow \infty$
* For all $i$, $\lvert h\_i(x) \rvert = O(x / (\log x)^2)$
* $x\_0$ is a constant

Note that $\lfloor b\_i x \rfloor = b\_i x - \\{b\_i x\\}$, and as the sawtooth function $\\{ u \\} = u - \lfloor u \rfloor$ is always between 0 and 1, replacing $\lfloor b\_i x \rfloor$ (or $\lceil b\_i x \rceil$ as appropiate) satisfies the conditions on the $h\_i$.

Find $p$ such that: $$ \sum\_{1 \le i \le k} a\_i b\_i^p = 1 $$ Then the asymptotic behaviour of $T(x)$ as $x \rightarrow \infty$ is given by: $$ T(x) = \Theta \left( x^p \left( 1 + \int\_{x\_1}^x \frac{g(u)}{u^{p + 1}} du \right) \right) $$ with $x\_1$ "large enough", i.e. there is $k\_1\>0$ so that $$g(x/2) \geq k\_1g(x) \tag{2}$$ for all $x\>x\_1$.

## Example A

As an example, take the recursion for $n \ge 5$, where $T(0) = T(1) = T(2) = T(3) = T(4) = 17$: $$ T(n) = 9 T(\lfloor n / 5 \rfloor) + T(\lceil 4 n / 5 \rceil) + 3 n \log n $$ The conditions are satisfied, we need $p$: $$ 9 \left( \frac{1}{5} \right)^p + \left( \frac{4}{5} \right)^p = 1 $$ As luck would have it, $p = 2$. Thus we have: $$ T(n) = \Theta \left( n^2 \left(1 + \int\_3^n \frac{3 u \log u}{u^3} du \right) \right) = \Theta(n^2)$$

since with $k\_1 \leq \frac{1}{2}\left(1 - \frac{\log 2}{\log 3}\right)$ we fulfill $(2)$ for all $x\geq 3$. Note that because the integral converges even if we use other constants, such as $1$, as lower bound, it is legal to use those as well; the difference vanishes in $\Theta$.

## Example B

Another example is the following for $n \ge 2$: $$ T(n) = 4 T(n / 2) + n^2 / \lg n $$ We have $g(n) = n^2 / \ln n = O(n^2)$, check. We have that there is a single $a\_1 = 4$, $b\_1 = 1 / 2$, which checks out. Assuming that the $n / 2$ is really $\lfloor n / 2 \rfloor$ and/or $\lceil n / 2 \rceil$, the implied $h\_i(n)$ also check out. So we need: $$ a\_1 b\_1^p = 4 \cdot (1 / 2)^p = 1 $$ Thus $p = 2$, and: $$ T(n) = \Theta\left(n^2 \left( 1 + \int\_2^n \frac{u^2 du}{u^3 \ln u} \right) \right) = \Theta\left(n^2 \left( 1 + \int\_2^n \frac{du}{u \ln u} \right) \right) = \Theta(n^2 \ln \ln n) $$ We apply a similar trick as above to the lower bound of the integral, only that we use $2$ because the integral does not converge for $1$.

(The help of maxima with the algebra is gratefully acknowledged)
> 15 votes

# Answer
# Summations

Often one encounters a recurrence of the form $$ T(n) = T(n-1) + f(n), $$ where $f(n)$ is monotone. In this case, we can expand $$ T(n) = T(c) + \sum\_{m=c+1}^n f(m), $$ and so given a starting value $T(c)$, in order to estimate $T(n)$ we need to estimate the sum $f(c+1) + \cdots + f(m)$.

# Non-decreasing $f(n)$

When $f(n)$ is monotone non-decreasing, we have the obvious bounds $$ f(n) \leq \sum\_{m=c+1}^n f(m) \leq (n-c) f(n). $$ These bounds are best-possible in the sense that they are tight for some functions: the upper bound for constant functions, and the lower bound for step functions ($f(m) = 1$ for $m \geq n$ and $f(m) = 0$ for $m \< n$). However, in many cases these estimates are not very helpful. For example, when $f(m) = m$, the lower bound is $n$ and the upper bound is $(n-c)n$, so they are quite far apart.

## Integration

A better estimate is given by integration: $$ \int\_c^n f(x) dx \leq \sum\_{m=c+1}^n f(m) \leq \int\_{c+1}^{n+1} f(x) dx. $$ For $f(m) = m$, this gives the correct value of the sum up to lower order terms: $$ \frac{1}{2} n^2 - \frac{1}{2} c^2 \leq \sum\_{m=c+1}^n m \leq \frac{1}{2} (n+1)^2 - \frac{1}{2} (c+1)^2. $$ When $f(m) = m$ we can calculate the sum explicitly, but in many cases explicit computation is hard. For example, when $f(m) = m\log m$ the antiderivative of $f$ is $(1/2) x^2\log x - (1/4) x^2$, and so $$ \sum\_{m=c+1}^n m\log m = \frac{1}{2} n^2 \log n \pm \Theta(n^2). $$

The Euler–Maclaurin formula gives better estimates. This formula can be used, for example, to prove strong forms of Stirling's formula, by estimating the sum $\log n! = \sum\_{m=1}^n \log m$.

# Non-increasing $f(n)$

In some cases, $f(n)$ is monotone non-increasing. The trivial estimates become $$ f(1) \leq \sum\_{m=c+1}^n f(m) \leq (n-c) f(1), $$ and the integral estimates $$ \int\_{c+1}^{n+1} f(x) dx \leq \sum\_{m=c+1}^n f(m) \leq \int\_c^n f(x) dx. $$ As an example, for $f(m) = 1/m$, using $\int f(m) = \log m$ we obtain $$ \sum\_{m=c+1}^n \frac{1}{m} = \log n \pm \Theta(1). $$
> 12 votes

# Answer
Sedgewick and Flajolet have done extensive work in analytic combinatorics, which allows recurrences to be solved asymptotically using a combination of generating functions and complex analysis. Their work allows many recurrences to be solved automatically, and has been implemented in some computer algebra systems.

This textbook on the subject was written by Flajolet and Sedgewick and is an excellent reference. A somewhat simpler exposition, geared towards applications to algorithm analysis, is this text by Sedgewick and Flajolet.

Hope this helps!
> 9 votes

# Answer
There may be times when you come across a strange recurrence like this: $$T(n) = \begin{cases} c & n \< 7\\ 2T\left(\frac{n}{5}\right) + 4T\left(\frac{n}{7}\right) + cn & n\geq 7 \end{cases}$$ If you're like me, you'll realize you can't use the Master Theorem and then you may think, "hmmm... maybe a recurrence tree analysis could work." Then you'd realize that the tree starts to get gross really fast. After some searching on the internet you see the Akra-Bazzi method will work! Then you actually start to look into it and realize you don't really want to do all the math. If you've been like me up till this point, you'll be excited to know there's an easier way.

---

# The Uneven Split Theorem Part 1

Let $c$ and $k$ be positive constants.

Then let $\\{a\_1, a\_2, \ldots, a\_k\\}$ be positive constants such that $\sum\_1^k a\_i \< 1$.

We also must have a recurrence of the form (like our example above):

$$\begin{align} T(n) & \leq c & 0 \< n \< \max\\{a\_1^{-1}, a\_2^{-1}, \ldots, a\_k^{-1}\\}\\ T(n) & \leq cn + T(a\_1 n) + T(a\_2 n) + \dots T(a\_k n) & n \geq \max\\{a\_1^{-1}, a\_2^{-1}, \ldots, a\_k^{-1}\\} \end{align}$$

## Claim

Then I claim $T(n) \leq bn$ where $b$ is a constant (e.g. asymptotically linear) and:

$$b = \frac{c}{1 - \left(\sum\_1^k a\_i\right)}$$

## Proof by Induction

**Basis**: $n \< \max\\{a\_1^{-1}, a\_2^{-1}, \ldots, a\_k^{-1}\\} \implies T(n) \leq c \< b \< bn$

**Induction**: Assume true for any $n' \< n$, we then have

$$\begin{align} T(n) & \leq cn + T(\lfloor a\_1 n \rfloor) + T(\lfloor a\_2 n \rfloor) + \dots + T(\lfloor a\_k n \rfloor)\\ & \leq cn + b \lfloor a\_1 n \rfloor + b \lfloor a\_2 n \rfloor + \dots + b \lfloor a\_k n \rfloor\\ & \leq cn + b a\_1 n + b a\_2 n + \dots + b a\_k n\\ & = cn + bn \sum\_1^k a\_i\\\\[0.5em\] & = \frac{cn - cn \sum\_1^k a\_i }{1 - \left(\sum\_1^k a\_i\right)} + \frac{cn \sum\_1^k a\_i}{1 - \left(\sum\_1^k a\_i\right)}\\\\[0.5em\] & = \frac{cn}{1 - \left(\sum\_1^k a\_i\right)}\\ & = bn & \square \end{align}$$

Then we have $T(n) \leq bn \implies T(n) = O(n)$.

## Example

$$T(n) = \begin{cases} c & n \< 7\\ 2T\left(\frac{n}{5}\right) + 4T\left(\frac{n}{7}\right) + cn & n\geq 7 \end{cases}$$ We first verify the coefficients inside the recursive calls sum to less than one: $$\begin{align} 1 & \> \sum\_1^k a\_i \\ & = \frac{1}{5} + \frac{1}{5} + \frac{1}{7} + \frac{1}{7} + \frac{1}{7} + \frac{1}{7}\\\\[0.5em\] & = \frac{2}{5} + \frac{4}{7}\\\\[0.5em\] & = \frac{34}{35} \end{align}$$

We next verify that the base case is less than the max of the inverses of the coefficients: $$\begin{align} n & \< \max\\{a\_1^{-1}, a\_2^{-1}, \ldots, a\_k^{-1}\\}\\ & = \max\\{5, 5, 7, 7, 7, 7\\}\\ & = 7 \end{align}$$

With these conditions met, we know $T(n) \leq bn$ where $b$ is a constant equal to: $$\begin{align} b &= \frac{c}{1 - \left(\sum\_1^k a\_i\right)}\\\\[0.5em\] &= \frac{c}{1 - \frac{34}{35}}\\\\[0.5em\] &= 35c \end{align}$$ Therefore we have: $$\begin{align} T(n) & \leq 35cn\\ \land\\; T(n) & \geq cn\\ \therefore T(n) & = \Theta(n) \end{align}$$

---

# The Uneven Split Theorem Part 2

Similarly we can prove a bound for when $\sum\_1^k = 1$. The proof will follow much of the same format:

Let $c$ and $k$ be positive constants such that $k \> 1$.

Then let $\\{a\_1, a\_2, \ldots, a\_k\\}$ be positive constants such that $\sum\_1^k a\_i = 1$.

We also must have a recurrence of the form (like our example above):

$$\begin{align} T(n) & \leq c & 0 \< n \< \max\\{a\_1^{-1}, a\_2^{-1}, \ldots, a\_k^{-1}\\}\\ T(n) & \leq cn + T(a\_1 n) + T(a\_2 n) + \dots T(a\_k n) & n \geq \max\\{a\_1^{-1}, a\_2^{-1}, \ldots, a\_k^{-1}\\} \end{align}$$

## Claim

Then I claim $T(n) \leq \alpha n \log\_k n + \beta n$ (we choose $\log$ base $k$ because $k$ will be the branching factor of the recursion tree) where $\alpha$ and $\beta$ are constants (e.g. asymptotically linearithmic) such that:

$$\beta = c$$ and $$\alpha = \frac{c}{\sum\_1^k a\_i \log\_k a\_i^{-1}}$$

## Proof by Induction

**Basis**: $n \< \max\\{a\_1^{-1}, a\_2^{-1}, \ldots, a\_k^{-1}\\} \implies T(n) \leq c = \beta \< \alpha n \log\_k n + \beta n$

**Induction**: Assume true for any $n' \< n$, we then have

$$\begin{align} T(n) & \leq cn + T(\lfloor a\_1 n \rfloor) + T(\lfloor a\_2 n \rfloor) + \dots + T(\lfloor a\_k n \rfloor)\\ & \leq cn + \sum\_1^k (\alpha a\_i n \log\_k a\_i n + \beta a\_i n)\\ & = cn + \alpha n\sum\_1^k (a\_i \log\_k a\_i n) + \beta n\sum\_1^k a\_i\\ & = cn + \alpha n\sum\_1^k \left(a\_i \log\_k \frac{n}{a\_i^{-1}}\right) + \beta n\\ & = cn + \alpha n\sum\_1^k (a\_i (\log\_k n - \log\_k a\_i^{-1})) + \beta n\\ & = cn + \alpha n\sum\_1^k a\_i \log\_k n - \alpha n\sum\_1^k a\_i \log\_k a\_i^{-1} + \beta n\\ & = \alpha n\sum\_1^k a\_i \log\_k n + \beta n\\ & = \alpha n \log\_k n + \beta n & \square \end{align}$$

Then we have $T(n) \leq \alpha n \log\_k n + \beta n \implies T(n) = O(n \log n)$.

## Example

Let's modify that previous example we used just a tiny bit: $$T(n) = \begin{cases} c & n \< 35\\ 2T\left(\frac{n}{5}\right) + 4T\left(\frac{n}{7}\right) + T\left(\frac{n}{35}\right)+ cn & n \geq 35 \end{cases}$$

We first verify the coefficients inside the recursive calls sum to one: $$\begin{align} 1 & = \sum\_1^k a\_i \\ & = \frac{1}{5} + \frac{1}{5} + \frac{1}{7} + \frac{1}{7} + \frac{1}{7} + \frac{1}{7} + \frac{1}{35}\\\\[0.5em\] & = \frac{2}{5} + \frac{4}{7} + \frac{1}{35}\\\\[0.5em\] & = \frac{35}{35} \end{align}$$

We next verify that the base case is less than the max of the inverses of the coefficients: $$\begin{align} n & \< \max\\{a\_1^{-1}, a\_2^{-1}, \ldots, a\_k^{-1}\\}\\ & = \max\\{5, 5, 7, 7, 7, 7, 35\\}\\ & = 35 \end{align}$$

With these conditions met, we know $T(n)\leq \alpha n \log n + \beta n $ where $\beta = c$ and $\alpha$ is a constant equal to: $$\begin{align} b &= \frac{c}{\sum\_1^k a\_i \log\_k a\_i^{-1}}\\\\[0.5em\] &= \frac{c}{\frac{2 \log\_7 5}{5} + \frac{4 \log\_7 7}{7} + \frac{\log\_7 35}{35}}\\\\[0.5em\] &\approx 1.048c \end{align}$$ Therefore we have: $$\begin{align} T(n) & \leq 1.048cn\log\_7 n + cn\\ \therefore T(n) & = O(n \log n) \end{align}$$
> 9 votes

# Answer
After checking this post again, I'm surprised this isn't on here yet.

# Domain Transformation / Change of Variables

When dealing with recurrences it's sometimes useful to be able to change your domain if it's unclear how deep the recursion stack will go.

For instance, take the following recurrence:

$$T(n) = T(2^{2^{\sqrt{\log \log n}}}) + \log \log \log n$$

How could we ever solve this? We could expand out the series, but I promise this will get gross really fast. Instead, let's consider how our input changes with each call.

We first have:

1. $n$, then
2. $2^{2^{\sqrt{\log \log n}}}$, then
3. $2^{2^{\sqrt{\log \log (2^{2^{\sqrt{\log \log n}}})}}}$, and so on.

The goal of a domain transformation will now be to change our recurrence into an equivalent $S(k)$ such that instead of the above transitions, we simply have $k, k-1, k-2, \ldots$.

For example, if we let $n = 2^{2^{2^{2^k}}}$, then this is what we get for our above recurrence: $$\begin{align\*} T(2^{2^{2^{2^k}}}) & = T(2^{2^{\sqrt{\log \log 2^{2^{2^{2^{k}}}}}}}) + \log \log \log (2^{2^{2^{2^{k}}}})\\ & = T(2^{2^{2^{2^{k-1}}}}) + 2^k \end{align\*}$$ Then we can simply rewrite it as: $$T(k) = T(k-1) + 2^k = \sum\_{i = 1}^{k} 2^k = 2^{k+1} - 1$$ Then all you have to do is convert $k$ back to $n$ to get: $$T(n) = 2^{(\log \log \log \log n) + 1} - 1 = O(\log \log \log n)$$

---

With this example, we can now see our goal.

Assume $$T(n) = \begin{cases} h(1) & n = 1\\ a\cdot T(f(n)) + h(n) & \mathrm{otherwise} \end{cases}$$ For some constant $a$ and functions $f(n)$ and $h(n)$.

We are now trying to find some function $g(k) = n$ and $f(g(k)) = g(k-1)$ such that $$\begin{align\*} T(g(k)) &= aT(f(g(k))) + h(g(k))\\ & = a\cdot T(g(k-1)) + h(g(k)) \end{align\*}$$

More generally, we want $f^{(i)}(n) = g(k - i)$ where $f^{(i)}(n)$ is the repeated application of $f$ on $n$, $i$ times. (e.g. $f^{(2)}(n) = f(f(n))$). This will allow $g(k)$ to act as the "iterating" function. Where, at depth $i$ of recursion, the work done is simply $h(g(k-i))$.

Then we can easily convert this to $S(k) = T(g(k))$ so that $$S(k) = a\cdot S(k-1) + h(g(k))$$ Then we only have to worry about summing up $h(g(k))$ for all $k$ up to a given base case. That is, $$S(k) = \sum\_{i = g^{-1}(1)}^{k} a^{k - i} h(g(i))$$

If we can determine $S(k) = \gamma(k)$ for some closed form $\gamma$ function, then we can determine $T(n)$ as $$T(n) = \gamma( g^{-1}(n))$$

Then we use this to get a bound on $T(n)$ via one of the other methods above. You could obviously modify this method a little bit to your specification, but in general you're trying to find an iterating function $g(k)$ to turn $T(n)$ into a simple recursion.

I don't know of an exact way to determine $g(k)$ at this point, but I will keep thinking about it and update if it becomes clearer (or if any commenter has some tips!). I have mostly found my $g(k)$ functions through trial and error in the past (see here, here, here, and here for examples).
> 9 votes

# Answer
Case 2 of the master theorem, as usually stated, handles only recurrences of the form $T(n) = aT(n/b) + f(n)$ in which $f(n) = \Theta(n^{\log\_ab}\log^k n)$ for $k \geq 0$. The following theorem, taken from a handout of Jeffrey Leon, gives the answer for negative $k$:

> Consider the recurrence $T(n) = a T(n/b) + f(n)$ with an appropriate base case.
>
> 1. If $f(n) = O(n^{\log\_b a} \log^{c-1} n)$ for $c \< 0$ then $T(n) = \Theta(n^{\log\_b a})$.
> 2. If $f(n) = \Theta(n^{\log\_b a} \log^{c-1} n)$ for $c = 0$ then $T(n) = \Theta(n^{\log\_b a} \log\log n)$.
> 3. If $f(n) = \Theta(n^{\log\_b a} \log^{c-1} n)$ for $c \> 0$ then $T(n) = \Theta(n^{\log\_b a} \log^c n$).

The proof uses the method of repeated substitution, as we now sketch. Suppose that $f(n) = n^{\log\_b a} \log\_b^{c-1} n$ and $T(1) = 0$. Then for $n$ a power of $b$, $$ T(n) = \sum\_{i=0}^{\log\_b n-1} a^i (nb^{-i})^{\log\_b a} \log\_b^{c-1} (nb^{-i}) = \\ \sum\_{i=0}^{\log\_b n-1} n^{\log\_b a} (\log\_b n - i)^{c-1} = n^{\log\_b a} \sum\_{j=1}^{\log\_b n} j^{c-1}. $$ Now let us consider the cases one by one. When $c \< 0$, the series $\sum\_{j=0}^\infty j^{c-1}$ converges, and so $T(n) = \Theta(n^{\log\_b a})$. When $c = 0$, the sum is the harmonic sum $H\_{\log\_b n} = \log(\log\_b n) + O(1)$, and so $T(n) = \Theta(n^{\log\_b a} \log \log n)$. When $c \> 0$, we can approximate the sum using an integral: $$ \sum\_{j=1}^{\log\_b n} \approx \int\_0^{\log\_b n} x^{c-1} \\, dx = \left. \frac{x^c}{c} \right|\_0^{\log\_b n} = \frac{\log\_b^c n}{c}, $$ and so $T(n) = \Theta(n^{\log\_b a} \log^c n)$.
> 7 votes

# Answer
There's one more approach that works for simple recurrence relations: ask Wolfram Alpha to solve the recurrence for you.

For instance, try typing `f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2)` into Wolfram Alpha. You'll get a solution, with a link to the Fibonacci numbers. Or try `f(1)=1, f(n)=f(n-1)+n` or `f(1)=1, f(n)=2*f(n-1)+3*n` or `f(n)=f(n-1) + 2 f(n-2), f(1)=1, f(2)=3` for other examples. However, be warned: Wolfram Alpha can solve some very simple recurrences, but it falls apart for more complex ones.

This approach avoids the need for any thinking, which can be viewed as either a bug or a feature.
> 6 votes

---
Tags: asymptotics, proof-techniques, combinatorics, recurrence-relation, reference-question
---


# Question
Title: Term for the tree of all paths starting from a given vertex in a graph
What is the term for the tree (or a part of the tree) of all possible paths in a graph that start from a given (source) vertex?

This is the tree that is implicitly or explicitly constructed when doing shortest path search. It appears, for example, in a lecture on search of an MIT Artificial Intelligence course, but I didn't understand if it has a name.

This is not a *search tree* and not really a *decision tree*.

Mathematically, it is a covering tree, but is there a more appropriate term in the context of shortest path search?

# Answer
> 1 votes
I've discovered that Nils Nilsson in *Principles of Artificial Intelligence* (1982) calls it just a *search tree*, and *search tree* is also used in *The Handbook of Artificial Intelligence* (1981) by Avron Barr and Edward Feigenbaum. I've also found a sufficiently recent paper *Predicting the size of IDA\*ʼs search tree* (2013).

I will stick with *search tree*.

# Answer
> 2 votes
It's the **self-avoiding walk tree** (SAW tree).

The trees seem to have been first considered by C.D. Godsil (*Matchings and Walks in Graphs*, *Journal of Graph Theory* 5(3):285–297, 1981; DOI link; just before Lemma 2.4), though Godsil doesn't use the name.

<sub>(And, yes, "self-avoiding walk" is just a mighty-long way of saying "path".)</sub>

---
Tags: terminology, trees, search-algorithms
---


# Question
Title: Asymptotic complexity of function with two Input variables
Suppose I have a function with two input below.

$f(m,n) = \log {n^m} + 100n \log \log {m^5} + 150m + 4n^2 + 1000$.

Is it safe to say that $f(m,n)$ is $\mathcal{O}(m \log n)$, or is it $\mathcal{O}(n^2)$ instead? I think the first one is more representative as it includes the variable $m$. But that may not be the case if $n$ is relatively very larger than $m$.

# Answer
No, it's not safe to say either. The intuition: When $n$ is really large, $f(m,n)$ grows faster than $O(m \log n)$. When $m$ is really large, $f(m,n)$ grows faster than $O(n^2)$.

Instead, what you can say is that $f(m,n)$ is $O(m \log n + n^2 + n \log \log m)$. Why?

$$\begin{align\*} f(m,n) &= \log {n^m} + 100n \log \log {m^5} + 150m + 4n^2 + 1000\\ &=m \log n + 100n\log \log m + 100n\log 5 + 150m + 4n^2 + 1000\\ &=O(m \log n) + O(n \log \log m) + O(n) + O(m) + O(n^2) + O(1)\\ &=O(m \log n) + O(n \log \log m) + O(n^2) + O(m \log n) + O(n^2) + O(1)\\ &=O(m \log n + n \log \log m + n^2). \end{align\*}$$

If $n \log \log m = O(m \log n + n^2)$ (I'm not sure if this is true), then you could simplify this to $O(m \log n + n^2)$.
> 2 votes

---
Tags: asymptotics
---


# Question
Title: Are there algorithms with proven upper bounds but no proven lower bound (above constant time)?
One of my professors mentioned such algorithms exist but could not think of any offhand. Obviously any algorithm will be at least $\mathcal{O(1)}$, but are there algorithms not yet proven to have a lower bound greater than this, which do have a proven upper bound?

I'm interested in both problems and algorithms, but in either case practical examples (if they exist) as opposed to artificial ones.

# Answer
> 2 votes
To try and answer your question:

Yes. generally lower bound is much harder to prove than upper bound. That is, to prove an upper bound, you must only show one algorithm that solves problem $A$ in $t\_1(n)$ time.

To prove a lower bound $t\_2(n)$ for the same problem $A$, you must show that ANY algorithm that solves $A$ MUST work in at least $t\_2(n)$ time.

Take the median for example (under the comparison model). There is a recursive algorithm that solves the median problem in $O(n)$ time. That means any greater upper bound is moot, and any greater lower bound is wrong.

However a precise lower bound for the median is an open question. The algorithm mentioned above performs $c\*n$ comparisons, where $c$ ~ $17$. It has been proven that for selection of median, a total of $\Omega(\frac{3n}{2})$ comparisons is required (which means a better algorithm does not exist).

However, we don't know if a greater lower bound exist. Proving a $\frac{5n}{2}$ comparisons lower bound is an open question!

---
Tags: algorithms, complexity-theory
---


# Question
Title: Mergable heap with no key knowledge cannot EXTRACT-MIN in $o(\log n)$ amortized time
We are looking into Fibonacci heaps in class at the moment, but I am stuck with this problem. Let $H$ be a mergable heap structure, by which is meant a data structure, where each element has a key, and that supports the following five operations (taken from CLRS):

MAKE-HEAP(): Creates and returns a new heap containing no elements.

INSERT($H$, $x$): Inserts element $x$ into $H$.

MIMIMUM($H$): Returns a pointer to the element in $H$ whose key is minimal.

EXTRACT-MIN($H$): Deletes the element from $H$, whose key is minimal, and returns a pointer to this element.

UNION($H\_1$, $H\_2$): Creates and returns a new heap that contains all elements of heaps $H\_1$ and $H\_2$.

Furthermore assume that $H$ cannot access the key values of its elements, but that it can only tell if tell if the key of one element is less than, equal to, or greater than the key of another element. Let $n$ be the number of operations performed on $H$.

There are two questions:

1) Show that if $H$ supports MAKE-HEAP and INSERT in $O(1)$ amortized time, then $H$ cannot also support EXTRACT-MIN in $o(\log n)$ amortized time (note little-oh).

2) Show that if $H$ supports MAKE-HEAP, INSERT and MINIMUM in $O(1)$ amortized time, then it cannot support DELETE in $o(\log n)$ time. Here DELETE($H$, $x$) is an operation that deletes the element $x$ from $H$.

I am not sure how to go about doing this, since there is no concrete data structure. It has something to do with $H$ only being able to compare keys, like any comparison based sorting algorithm must run in $\Omega(n\log n)$.

# Answer
1) The answer is very simple. Assume it can support $delete min$ in less than $log(n)$ time. That means your structure $H$ can sort $n$ elements via comparisons in under $nlog(n)$ time (simply insert all, then $delete min$ $n$ times), which conflicts with the comparison model lower bound.

2) Same as 1. if you can tell who is the minimum element in $O(1)$ and delete it, you can select and delete the minimum $n$ times and therefore sort in under $nlog(n)$ time.
> 1 votes

---
Tags: data-structures, runtime-analysis, heaps
---


# Question
Title: Language involving irrational number is not a CFL
I am working through a hard exercise in a textbook, and I just can't figure out how to proceed. Here is the problem. Suppose we have the language $L = \\{a^ib^j: i \leq j \gamma, i\geq 0, j\geq 1\\}$ where $\gamma$ is some irrational number. How would I prove that $L$ is not a context-free language?

In the case when $\gamma$ is rational, it's pretty easy to construct a grammar that accepts the language. But because $\gamma$ is irrational, I don't really know what to do. It doesn't look like any of the pumping lemmas would work here. Maybe Parikh's theorem would work here, since it would intuitively seem like this language doesn't have an accompanying semilinear Parikh image.

This exercise is from "A Second Course in Formal Languages and Automata Theory" by Jeffrey Shallit, Exercise 25 of Chapter 4.

I would really appreciate any help, or nudges in the right direction. Thank you!

# Answer
> 7 votes
According to Parikh's theorem, if $L$ were context-free then the set $M = \\{(a,b) : a \leq \gamma b \\}$ would be semilinear, that is, it would be the union of finitely many sets of the form $S = u\_0 + \mathbb{N} u\_1 + \cdots + \mathbb{N} u\_\ell$, for some $u\_i = (a\_i,b\_i)$.

Obviously $u\_0 \in M$, and moreover $u\_i \in M$ for each $i \> 0$, since otherwise $u\_0 + N u\_i \notin M$ for large enough $N$. Therefore $g(S) := \max(a\_0/b\_0,\ldots,a\_\ell/b\_\ell) \< \gamma$ (since $g(S)$ is rational). This means that every $(a,b) \in S$ satisfies $a/b \leq g(S)$.

Now suppose that $M$ is the union of $S^{(1)},\ldots,S^{(m)}$, and define $g = \max(g(S^{(1)}),\ldots,g(S^{(m)})) \< \gamma$. The foregoing shows that every $(a,b)$ in the union satisfies $a/b \leq g \< \gamma$, and we obtain a contradiction, since $\sup \\{ a/b : (a,b) \in M \\} = \gamma$.

---

When $\gamma$ is rational, the proof fails, and indeed $M$ is semilinear: $$ \\{ (a,b) : a \leq \tfrac{s}{t} b \\} = \bigcup\_{a=0}^{s-1} (a,\lceil \tfrac{t}{s} a \rceil) + \mathbb{N} (s,t) + \mathbb{N} (0,1). $$ Indeed, by construction, any pair $(a,b)$ in the right-hand side satisfies $a \leq \tfrac{s}{t} b$ (since $s = \tfrac{s}{t} t$). Conversely, suppose that $a \leq \frac{s}{t} b$. While $a \geq s$ and $b \geq t$, subtract $(s,t)$ from $(a,b)$. Eventually $a \< s$ (since $b \< t$ implies $a \leq \frac{s}{t}b \< s$). Since $a \leq \frac{s}{t} b$, necessarily $b \geq \lceil \tfrac{t}{s} a \rceil$. Hence we can subtract $(0,1)$ from $(a,b)$ until we reach $(a,\lceil \tfrac{t}{s} a \rceil)$.

# Answer
> 6 votes
Every variable except $\gamma$ in this answer stands for a positive integer. It is well-known that given an irrational $\gamma\>0$, there is a sequence of rational numbers $\dfrac{a\_1}{b\_1}\lt\dfrac{a\_2}{b\_2}\lt\dfrac{a\_3}{b\_3}\lt\cdots \lt\gamma$ such that $\dfrac{a\_i}{b\_i}$ is nearer to $\gamma$ than any other rational number smaller than $\gamma$ whose denominator is less than $b\_i$.

---

It turns out that the pumping lemma does work!

For the sake of contradiction, let $p$ be the pumping length of $L$ as a context-free language. Let $s=a^{a\_p}b^{b\_p}$, a word that is $L$ but "barely". Note that $|s|\>b\_p\ge p$. Consider $s=uvwxy$, where $|vx|\> 1$ and $s\_n=uv^nwx^ny\in L$ for all $n\ge0$.

Let $t\_a$ and $t\_b$ be the number of $a$s and $b$s in $vx$ respectively.

* If $t\_b=0$ or $\dfrac{t\_a}{t\_b}\gt\gamma$, for $n$ large enough, the ratio of the number of $a$s to that of $b$s in $s\_n$ will be larger than $\gamma$, i.e., $s\_n\not\in L$.
* Otherwise, $\dfrac{t\_a}{t\_b}\lt\gamma$. Since $t\_b\<b\_p$, $\dfrac{t\_a}{t\_b}\lt \dfrac{a\_p}{b\_p}$. Hence, $\dfrac{a\_p-t\_a}{b\_p-t\_b}\>\dfrac{a\_p}{b\_p}$ Since $b\_p-t\_b\<b\_p$, $\dfrac{a\_p-t\_a}{b\_p-t\_b}\>\gamma,$ which says that $s\_0\not\in L$.

The above contradiction shows that $L$ cannot be context-free.

---

Here are two related easier exercises.

**Exercise 1.** Show that $L\_\gamma=\\{a^{\lfloor i \gamma\rfloor}: i\in\Bbb N\\}$ is not context-free where $\gamma$ is an irrational number.

**Exercise 2.** Show that $L\_\gamma=\\{a^ib^j: i \leq j \gamma, i \ge0, j\ge 0\\}$ is context-free where $\gamma$ is a rational number.

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


# Question
Title: Grouping/Clustering results based on shared values
I have a data set that is similar to this:

* 10,000 jobs with 200,000 applicants which are linked to a job.

I'm looking to cluster the shared jobs based on applicants that they share, am I reinventing the wheel looking to build this or is there a common solution?

Most of the example I found all require a "distance" but I can't see how I could compute one in this case?

**Edit:** To add, the clustering criteria would be fairly straightforward more than X applicants (say 5) in common, with only a single cluster per job.

# Answer
You could use the Jaccard distance to compare two jobs: i.e., the distance between two jobs is

$$d(A,B) = {|A \cap B| \over |A \cup B|},$$

where $A$ is the set of applicants for the first job and $B$ is the set of applicants for the second job. Then, use any standard clustering algorithm with this distance measure.
> 1 votes

---
Tags: clustering
---


# Question
Title: Finding topologically sorted connected components in directed acyclic graph
I am aware topological sort and connected component algorithms are very related, but I have been looking for an algorithm to simultaneously compute both, rather than one after the other, and I am finding it surprisingly hard.

Assuming a directed acyclic graph, is it possible to simultaneously find the list of connected components while at the same time topologically sorting the nodes in each of the components?

To clarify, the output would be a list of components, where each component is a topological order of the nodes contained in that component.

Bonus points if the list of connected components is sorted following the insertion order of nodes in the graph (i.e. the first connected component will contain the first node ever inserted in the graph, *regardless* of global topological order; etc for subsequent components).

# Answer
Standard algorithms for computing strongly connected components label each vertex with a number indicating which component it is part of. Then, you can use that to construct the "metagraph" of components (where each component of the graph is a vertex of the metagraph, and there is an edge $i \to j$ in the metagraph iff there is an edge $v \to w$ in the original graph where $v$ is in component $i$ and $w$ is in component $j$) in linear time. Finally, you can apply a topological sorting algorithm on the metagraph.

Some algorithms for computing strongly connected components (such as Tarjan's algorithm) already do that for you for free. Or, you can do it yourself as a postprocessing phase; since it takes only linear time, it won't increase the asymptotic running time of the algorithm.

See, e.g., https://en.wikipedia.org/wiki/Strongly\_connected\_component, https://en.wikipedia.org/wiki/Kosaraju%27s\_algorithm, and https://en.wikipedia.org/wiki/Tarjan%27s\_strongly\_connected\_components\_algorithm.
> 3 votes

---
Tags: graphs, graph-traversal
---


# Question
Title: checking whether a language is turing recognizable
After reading about it in the textbook and in the web, i was wondering about the "turing recognizable" concept.

so for instance, if i take a simple language like:"L = {\< M \> | M ACCEPTS \< M \>}", then it should be a turing recognizable language since there can be a turing machine that halts and accepts strings in it, and for strings not in that language it doesn't halt or just skip them.

however, how can i build such a turing machine(i mean the pseudocode for it)?

i know it's quite a simple question, but i rose it out of curiosity so i could learn and from that to adapt to more complicated problems.

thank you very much for helping me

# Answer
> 2 votes
Let $U$ be a universal Turing machine. Then running $U$ on the input $\langle M \rangle, x$ will produce the same output as running $M$ on the input $x$ -- that's what it means for $U$ to be a universal Turing machine. Others have shown how to build a universal Turing machine.

Then, you can build a Turing machine to do what you want by using $U$: namely, on input $\langle M \rangle$, your Turing machine should run $U(\langle M \rangle, \langle M \rangle)$. Or, to put it another way, your Turing machine should make a second copy of the input it receives on the input tape, then run $U$. If you know how to build a Turing machine to copy a bit-string, and if you have a universal Turing machine $U$, you'll have a solution for your problem.

This might not sound very enlightening, but it's the easiest way to describe how you can do it. Programming Turing machines is incredibly tedious and usually not enlightening: it's like programming in a particularly nasty and human-unfriendly programming languages. Therefore, it's best avoided wherever possible. In this case, my solution lets you take advantage of the fact that someone else has already figured out how to build a universal Turing machine.

You might be wonder how to do that. Well, the basic idea is that you need to implement an interpreter for Turing machines. Pick your favorite programming language, like Python; could you write a Python program to interpret a Turing machine, one step at a time? I bet you could -- it's a simple matter of programming. Now you just need to do that, but this time instead of writing a Python program, you need to write a Turing machine -- a nastier and messier task that's far more tedious, but not conceptually different.

---
Tags: complexity-theory, turing-machines, computability
---


# Question
Title: Validity of □(P→ Q) → (◊P → ◊Q) in linear temporal logic
How can I prove that $\Box(P\rightarrow Q)\rightarrow (\Diamond P\rightarrow\Diamond Q)$ is valid in linear temporal logic (LTL)?

# Answer
> 4 votes
Think about what the formula means. The first part says that it's always true that $P$ implies $Q$; the second part says that, if $P$ is true somewhere, then $Q$ must be true somewhere, too. Well, if $P$ implies $Q$ then, if $P$ is true somewhere, then $Q$ had better be true in that place, too!

# Answer
> 1 votes
Take this with a grain of salt, since I'm not sure what sort of inference rules you're allowed to use. Assuming the domain D is times t with standard ordering, I'd say:

1. □(P→Q)
Assume for conditional proof, i.e. P→Q is true at any t in D
2. ◊P
Assume for conditional proof, i.e. P is true at some t in D
3. P
◊-Elimination on line 2, i.e. index at t1 where P is true
4. P→Q
□-Elimination on line 1, i.e. at t1 since P→Q true at any t in D
5. Q
MP on lines 3 and 4, at t1
6. ◊Q
◊P-Introduction on line 5, at t1
7. ◊P→◊Q
Discharge ◊P for conditional proof
8. □(P→Q)→◊P→◊Q
Discharge □(P→Q) for conditional proof

Note, in one of the comments it was suggested proving □P→◊P might help. Here's a proof of that:

1. □P
Assume for conditional proof
2. P
□-Elimination on line 1, at time t2
3. ◊P
◊-Introduction on line 2, at t2
4. □P→◊P
Discharge □P for conditional proof

Then by substitution, you can infer □(P→Q)→◊(P→Q). Call this **T-Replacement**. But I don't think that would be useful in proving □(P→Q)→◊P→◊Q. To see why, suppose you've inferred ◊(P→Q) from □(P→Q) by T-Replacement. Then:

1. ◊(P→Q)
From T-Replacement
2. ◊P
Assume for conditional proof
3. P
◊-Elimination on line 2, i.e. index at t3 where P→Q is true
4. P→Q
◊-Elimination on line 1, i.e. index at *t4* where P→Q is true

But you can't combine lines 3 and 4 to use MP since they're indexed to different times. I don't think you can infer ◊P→◊Q from ◊(P→Q).

# Answer
> 0 votes
I suggest 2 methods to prove validity of $\Phi$:

1. Proof by contradiction. Assume we can falsify $\Phi$, prove that actually it is impossible to achieve.The clue in https://cs.stackexchange.com/a/101284/88420 shows how to do it.
2. Assume $\Phi$ valid, prove the unsatisfiability of $\neg \Phi$. Using a calculi probably we should derive $\phi \wedge \neg \phi$. A tool can confirm it, but I couldn't derive it by hand.

---
Tags: logic, linear-temporal-logic
---


# Question
Title: Longest common sequence matrix giving wrong answer
I am trying to find longest common sequence for these two strings

```
SHINCHAN
NOHARAAA

```

The common sequence is `NHA` of length 3

But when I am trying to find out this through LCS matrix which I learnt from this link https://en.wikipedia.org/wiki/Longest\_common\_subsequence\_problem

Based on the explanation and this example given there

I built this matrix for my case

But my matrix is reaching to the length 6 while it should reach to length 3 only because that is the longest comment sequence of the two strings I am using.

Could anybody please point out the mistake I am doing? I can see the problem is happening because of the extra 3 A's at the end of one of the string.

# Answer
> 1 votes
Look at row=1 and column=8 (using 0 indexed numbers) in your matrix. That value says that the length of LCS between `SHINCHAN` and `N` is 2, which is impossible since `N` itself is of size 1.

When s1\[i\] and s2\[j\] are equal you need to look at the number in matrix\[i-1\]\[j-1\] and add one and not matrix\[i\]\[j-1\] (which I think you are doing). You can compare your method to the pseudocode written in the wikipedia article to arrive at the correct matrix (copied below for convenience)

```
function LCSLength(X[1..m], Y[1..n])
    C = array(0..m, 0..n)
    for i := 0..m
       C[i,0] = 0
    for j := 0..n
       C[0,j] = 0
    for i := 1..m
        for j := 1..n
            if X[i] = Y[j]
                C[i,j] := C[i-1,j-1] + 1
            else
                C[i,j] := max(C[i,j-1], C[i-1,j])
    return C[m,n]

```

---
Tags: algorithms, longest-common-substring
---


# Question
Title: What is wrong with this solution for $\mathcal{O}({\log({n \choose \frac{n}{2}})})$?
In this recitation on MIT OCW, the instructor uses Stirling's approximation to calculate that

$\mathcal{O}({\log({n \choose \frac{n}{2}})}) = \mathcal{O}(n)$.

However, I went through the following steps to conclude that $\mathcal{O}({\log({n \choose \frac{n}{2}})}) = \mathcal{O}(\log{n})$. Where did I go wrong?

First, note that ${n \choose \frac{n}{2}} = \frac{n!}{\frac{n}{2}!\frac{n}{2}!}$. By basic logarithm laws, we get that this is equal to $\log{(n!)} - \log{(\frac{n}{2}!\frac{n}{2}!)}$. From this it follows that:

$$ \mathcal{O}(\log{(n!)} - \log{(\frac{n}{2}!\frac{n}{2}!)})\\ = \mathcal{O}(\log{(n!)}) \\ = \mathcal{O}\Big(\log{\big(n(n-1)(n-2)\cdots(1)\big)}\Big) \\ = \mathcal{O}\Big(\log{n} + \log{(n-1)} + \ldots + \log{(1))}\Big) = \mathcal{O}(\log{n}) $$

So, what is wrong here? I've gone over it for a while and I can't see any mistakes. Plotting these functions, though, I can see quite clearly that there must be a mistake.

# Answer
> $\mathcal{O}\Big(\log{n} + \log{(n-1)} + \ldots + \log{(1))}\Big) = \mathcal{O}(\log{n})$

That is not right. When $n$ is large enough,

$$\begin{align} \log{n} + \log{(n-1)} + \ldots + \log(1) &\ge \log{n} + \log{(n-1)} + \ldots + \log(n/2)\\ &\ge n/2 \log(n/2)\\ &=\Theta(n\log n) \end{align}$$

More precisely, since $n!\sim {\sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}}$ by Stirling's approximation,

$$\begin{align} \log{n} + \log{(n-1)} + \ldots + \log(1) &=\log(n!)\\ &\sim \log\left({\sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}}\right) \\ &\sim n(\log(n) -1) \\ &\sim n\log(n) \end{align}$$

You can take a moment to try understanding intuitively why $$\lim\_{n\to\infty}\frac {\log(n!)}{\log (n^n)} = 1.$$
> 3 votes

# Answer
The last step is incorrect. $\mathcal{O}\Big(\log{n} + \log{(n-1)} + \ldots + \log{(1))}\Big)$ is not $\mathcal{O}(\log{n})$. You made the same mistake as What goes wrong with sums of Landau terms?. See also What is the asymptotic runtime of this nested loop?.
> 2 votes

---
Tags: complexity-theory, asymptotics, landau-notation
---


# Question
Title: Understanding the relations between O(g(n)), Θ(g(n)) and Ω(g(n))
I was reading the Cormen, Leiserson, Rivest and Stein textbook, *Introduction to Algorithms*.

The book explained the three asymptotic notations literally very well. However, there was this paragraph:

> Technically, it is an abuse to say that the running time of insertion sort is $O(n^2)$, since for a given $n$, the actual running time varies, depending on the particular input of size $n$.

and this one:

> It is not contradictory, however, to say that the worst-case running time of insertion sort is $Ω(n^2)$, since there exists an input that causes the algorithm to take $Ω(n^2)$ time.

1. I understand why did the author said that "it is an abuse to say $O(n^2)$ is the running time", as there are the inputs with best cases causing linear time and there are also inputs with worst case causing quadratic time.
2. I don't understand why it is not contradictory to say that the worst-case running time of insertion sort is $Ω(n^2)$. Isn't $\Omega(g(n))$ supposed to be the best running time? So should it not be $Ω(n)$?

It confuses me. Can you please explain why $Ω(n^2)$ is possible for insertion sort when it should be $Ω(n)$?

# Answer
> Aren't $\Omega(g(n))$ supposed to tell best running time?

**Not at all**. It just means that for all large enough $n$, there exist inputs of size $n$ where the algorithm takes time at least proportional to $g(n)$.

> Can you please explain why $\Omega(n^2)$ is possible for insertion sort when it should be $\Omega(n)$?

The **worst-case** running time of insertion sort is $\Omega(n^2)$ because for all $n$, **there exist** inputs of size $n$ where it takes time proportional to $n^2$.

The running time of insertion sort in general is not **always** $\Omega(n^2)$, as you observed; it depends on the input. But the **worst-case** running time (which does not depend on the input, only on $n$) is $\Omega(n^2)$.
> 1 votes

---
Tags: time-complexity, asymptotics
---


# Question
Title: How to prove that the time complexity of this algorithm is O($\sqrt{N}$)?
```
  int n;
  cin >> n;
  int sum = 0;
  for (int i = 1; sum <= n; i++) {
      sum += i;
  }

```

If I assumed that $N = 100$, the loop will run $13$ steps, which is almost the square root of $N$, if $N = 10000$, the loop will run $141$ steps, which is almost the square root of $N$, but I don't know how to prove that, I only know it by intuition

# Answer
The loop iterates $k$ times, where $k$ is minimal such that $\sum\_{i=1}^k i\>n$. We know that $\sum\_{i=1}^k i = \tfrac12k(k+1)$, so you just need to solve for $k$.
> 6 votes

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


# Question
Title: Time complexity of recurrence function with if statement
Given the following code.

```
public static int fc(int n, int p) {
    if (p == 0) {
        return 1;
    } if (p % 2 == 0) {
        int a = fc(n, p / 2);
        return a * a;
    } return n * fc(n, p - 1);
}

```

How to calculate the time complexity of this code in big-$\mathcal{O}$ notation? I already define the recurrence function, which is

\begin{equation} T(p) = \begin{cases} 1, & \text{if}\ p=0 \\ T(p/2) + 1, & \text{if } p \text{ is even} \\ T(p-1) + 1, & \text{if } p \text{ is odd} \end{cases} \end{equation}

Assuming that $p = 2^k$, then $T(p) = T(2^k) = T(2^{k-1}) + 1$. By backwards substitution, the equation become $T(2^k) = T(2^{k-n}) + n$. When $k = n$, $T(2^k) = T(1) + k = 1 + \log p$. Thus, $T(p) = \mathcal{O}(\log p)$.

However, I think that it only holds for the best case. I want to know about the other cases as well. How do I prove the average and worst case for this code?

# Answer
> 1 votes
Let us prove by induction the following formula:

> $T(n)$ is the number of 0s in the binary representation of $n$, plus twice the number of 1s.

This certainly holds for $n = 0$. If $n$ is even, then $T(n) = T(n/2) + 1$, and indeed the binary representation of $n/2$ differs from that of $n$ by having one less 0. If $n$ is odd, then $T(n) = T(n-1) + 1$, and indeed the binary representation of $n-1$ differs from that of $n$ by having one 1 replaced by 0.

This shows that $T(n) = O(\log n)$. It is not clear what you mean by average case, but the formula above should let you work that out. For example, let us consider the $2^{m-1}$ numbers of length exactly $m$. Each of them has a leading 1, and the other $n-1$ bits are half 0, half 1 (considering all numbers in the range). Hence the average value of $T$ for $2^{m-1} \leq n \< 2^m$ is $m + 1 + \frac{m-1}{2} = \frac{3m+1}{2}$. Using this, we can compute the average value of $T$ for $0 \leq n \< 2^m$ to be $$ \frac{T(0)}{2^m} + \sum\_{\ell=1}^m 2^{\ell-1-m}\frac{T(2^{\ell-1}) + \cdots + T(2^\ell-1)}{2^{\ell-1}} = \frac{1}{2^m} + \sum\_{\ell=1}^m 2^{\ell-1-m} \frac{3\ell+1}{2} = \frac{3}{2}m - 1 + \frac{1}{2^{m-1}}. $$

---
Tags: asymptotics
---


# Question
Title: Context free grammar for L={ ((ab)^n)^m }
I want to write a cfg for the following language:

$ L = {((ab)^n)^m }$ $m,n \>= 0$

this language produces (abababababab) where:
$n=2, m=3 \\ or \\ n=3, m=2$

I have no idea what to do with it!

# Answer
No need for a CFG: this language is regular!

$$L = (ab)^\*$$

Any number of $ab$s is in the language: just set $n$ to 1, and $m$ to the number of repetitions. So all you need is a Kleene star.

If you really want a CFG, you can do it like this:

$$S \rightarrow SX \mid \varepsilon$$ $$X \rightarrow ab$$

This is the "standard" way of translating a Kleene star into a CFG.
> 3 votes

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


# Question
Title: Turing Machine remembering copied symbols
So, I know that any multiple-tape TM can be in theory turned into a one-tape TM. However, it is too easy to copy, let's say, binary numbers from one tape to another. That's why I thought about putting a separator between the two copies and then taking symbols one after the other and writing them after the separator until the separator itself is encountered. The problem, however, is that I am not sure how it could remember places where it has already been/copied the characters. Example:

First we have:

```
##1011##

```

Then we put the separator '&' at the end

```
##1011&##

```

Read back to beginning and change the state accordingly so that it will write $1$ or $0$ after the separator. So far, so good, then we read back again, and now:

*How could we know that we have already copied the first $1$ and must now copy the $0$ without putting any restriction on the input length* (in regards to the number of states)? In other words, how could we remember the last copied symbol?

I have thought of putting an extra parameter - just a integer ≤ length (something like $\delta (z\_1,1,L,1)$ where the last one would be the number of already written-out symbols). This would be easy to understand, but would be nowhere near the definition of Turing machine. So, any useful ideas?

Thanks.

# Answer
> 1 votes
Once you've hit the '&' separator, move left until you see the '#', then move one cell to the right and replace the '1' with an 'x' (and change to state $p$ to "remember" you've seen a 1) or a '0' with a 'y' (changing to state $q$ to "remember" you've seen a 0). Now move right until you pass the '&' separator and see a '#'. Replace that with a '1' if you were in state $q$ or with a '0' if you were in state $p$. Now move to the left until you see a 'x' or a 'y', move one cell to the right and repeat what you've done before. Continue the process until everything on the left is a string of 'x's and 'y's, then make one more pass, restoring the values to their originals.

# Answer
> 0 votes
Remember that Turing machines were designed as, essentially, a simulation of what a person could do with pencil and paper. That's what it meant to be a computer in those days: a person who computes!

So, how would you copy a long string of zeroes and ones using a pencil and paper? You'd probably do something like this:

* read the first character and remember what it is;
* put a pencil mark by that character to say that it's been copied;
* write a copy of the character in the place you're copying to;
* go back to the first unmarked character and repeat until you've marked every character;
* go back and erase all the marks.

And that's how you do it with a Turing machine, too.

---
Tags: turing-machines, automata
---


# Question
Title: Augmenting a tree such that we preserve the insertion operation optimal runtime
Suppose we are given a red-black tree with $n$ vertices with distinct keys and we want to store, as addition information in each vertex $v$, the biggest key out of the keys that are smaller than $v$ (or nothing if it doesn't exist). Can we insert a new element in this tree in $O(\log n)$ time?

I think that we can. My idea is that while traversing the tree in order to determine where to insert the new element, we could just update this additional information for every vertex that we encounter. The problem with this is that we may not update all the required vertices, for instance:

```
        (80)
      /      \
    (1)      (81)
   /   \     /   \
  (0) (79) (77)  (82)

```

Here, if we would try to insert $76$, we would not update the additional information in the vertex with value $77$ if we use the method I described above.

I would like strongly appreciate hints to improve my solution (mostly I would want only hints).

# Answer
> 0 votes
I think you mean $successor$ & $predecessor $.

Formally: $predecessor(v): x $ s.t $ x \leq v$ (or smaller if your keys are distinct) and no $y$ exists in your structure s.t $y \leq v$ and $y \> x $

Symmetrical definition for $successor(v)$.

You can apply several methods for each node to know its $successor/predecessor $ in $O(1)$ time. A simple option is pointers - you "pay" $log(n)$ while inserting, pay another $log(n)$ to find $successor/predecessor$, and update the corresponding fields.

A doubly linked list would work just as well (in which case you save pointers to the list in the tree nodes, from which you can go to next or previous list node for successor/ predecessor respectively)

btw, your example is wrong. the key '77' cannot be in the right subtree of '80'

---
Tags: data-structures, binary-search-trees, red-black-trees
---


# Question
Title: How does the bitlength of the divisor affect the running-time complexity of division algorithms?
Wikipedia lists $O(M(n))$ as the best complexity (out of the algorithms listed) for division on two $n$-digit numbers, where $M(n)$ is the complexity of the multiplication algorithm of choice. This is the complexity of the Newton-Raphson division.

My question is this: what are some of the best known (wrt. running-time complexity as a function of $n$) algorithms for division of two numbers, of m, and $n \< m$ digits respectively? That is, how much complexity can be gained when the two numbers are not assumed to be of the same length?

I wouldn't want to treat $n$ as a constant as I'm in particularly interested in the case of $n \in O(\log{m})$. So I'm not looking for answers that treat $n$ as in $O(1)$.

# Answer
Let $M(m, n)$ and $D(m, n)$, respectively, be the costs of multiplying and dividing an $m$-digit number by an $n$-digit number (with $m \ge n$). Brent and Zimmermann give the following bounds:

$$ (1) \qquad M(m,n) \le \left\lceil \frac{m}{n} \right\rceil M(n) $$ $$ (2) \qquad M(m,n) \le M \left( \frac{m+n}{2} \right) (1+ o(1)) $$ $$ (3) \qquad D(m+n,n) \le O(M(m,n)) $$ where $M(n)$ is the complexity of balanced $n$-digit multiplication.

I am not an expert in this area but I can try to summarize their explanations:

(1) is based on the idea that if $m = kn$, you can cut the larger operand into $k$ pieces, giving $M(kn, n) = k M(n) + O(kn)$.

(2) is based on using an evaluation-interpolation scheme and reducing the unbalanced multiplication to a balanced multiplication of two $(m+n)/2$-digit numbers (I realize this is a bit vague, but they don't give much details in this case).

(3) they also don't give a reference in this case; judging from the bound, it may be based on using Newton to compute the reciprocal of the $n$-digit number and then multiplication. One unbalanced division algorithm they do discuss explicitly is based on computing $n$ digits of the quotient at a time, reducing the division to several $2n$ by $n$ divisions, each of which is implemented with the recursive division algorithm. However, the latter does not seem to fit the bound (3).

For the details, have a look at Sections 1.3.5, 1.4.3, and the table at the end of their monograph.
> 4 votes

# Answer
Division of m bit numbers by n bit numbers with n ≤ $N\_0$ for some fixed $N\_0$ can always be done in O (m).

I think division will work in m * O (log n). Roughly, you calculate 1/n, then you do something like long division doing m / n steps each taking O (n log n) time.
> 0 votes

---
Tags: complexity-theory, time-complexity, arithmetic, number-theory
---


# Question
Title: Solving a in/equality constraint problem with graph search
You are given a list of m constraints over n distinct variables x1, ..., xn. Each constraint is of one of the following two types.

1. An equality constraint of the form xi = xj for some i!=j.
2. An inequality constraint of the form xi!= xj for some i!=j.

I want to find an assignment, if it exists, for each variable such that it conforms to all the constraints using a graph search algorithm in O(m+n) time.

This reminds me of the graph colouring problem, however that only involves checking graph neighbours where as in any efficient graph I could think of, the nodes sharing a constraint may not be neighbours.

My first thought was to create a graph such that all nodes that equal are connected then use DFS to traverse each node and check if it has an inequality with a parent, however that doesn't seem very efficient as for every node (m) I have to traverse every inequality constraint (at most n) which brings me to nm time, where as DFS inherently has O(m+n)on an ideal representation.

Any clues?

# Answer
> 0 votes
Let there be K equalities.

1. Create a forest of n nodes stored in an adjacency list O(n)
2. For each equality between Xi and Xj, add an edge between them. O(2k)
3. Call DFS on any node. O(|m| +|n|)
    1. DFS has a counter that starts at 0
    2. When DFS visits a node it sets that node’s value to the current value of its counter
    3. When DFS crosses a cross-edge, it increments it’s counter by 1
4. For each inequality between Xi and Xj, check their values assigned by the counter during the DFS, if they are equal return NIL O(2(m - k))
5. Create the result array by going through the adjacency list and setting the value at index j of the node X\_j O(n) =\> Worst case time complexity O(3|m| + 3|n|) =\> O(|m| + |n|)

# Answer
> 1 votes
You're on the right track. Construct an undirected graph with an edge for each equality constraint, as you suggested. Next, look into the concept of connected components, and algorithms for finding them. You should be able to take it from here.

This problem can be solved in linear time.

---
Tags: graphs, graph-traversal, constraint-satisfaction
---


# Question
Title: Why do ¬, ∀ and ∃ have the same precedence?
I thought the order of precedence of operators and quantifiers was arbitrary, but I don't really understand why those three have the same "strength" in relation to other operators (e.g., ¬ will have precedence over ∧, but not over ∀). This leads to the rule being that ¬, ∀ and ∃ will bind to the closest predicate on their right (if I understood correctly). Why is this?

# Answer
> I thought the order of precedence of operators and quantifiers was arbitrary

Certainly the rules of precedence could be set up in different ways, but some ways are more helpful and convenient than others, and there are principled reasons for this.

> but I don't really understand why those three have the same "strength" in relation to other operators (e.g., ¬ will have precedence over ∧, but not over ∀).

Assuming you mean "strength" as a synonym for "precedence," the reason these three have the same precedence is that these operators are all **prefix** operators: as you said, their arguments are the next expressions to the right. ¬ takes the next expression as its single argument, and ∀ and ∃ each take the next two expressions. As long as you use only prefix operators, there is never ambiguity as to which operators govern which arguments: There is only one possible answer to "What's the argument of $\neg$ in $\neg \forall x \forall y P(x, y)$?" As such, precedence rules between these prefix operators would be unnecessary.

On the other hand, when you introduce **infix** operators such as ∧ (or mix in postfix operators), parsing becomes ambiguous without precedence rules or parentheses. For example, $\neg A \land B$ would be ambiguous because $\neg$ is a prefix operator and $\land$ is an infix operator. To fix this, we could just use parentheses, but in a complex expression this becomes cumbersome. Precedence rules, if agreed upon, allow us to be unambiguous with less notation. By following the rule "¬ will have precedence over ∧", we can write and read "$\neg A \land B$" and agree on what it means.

> This leads to the rule being that ¬, ∀ and ∃ will bind to the closest predicate on their right (if I understood correctly). Why is this?

I think the chain of "leading" here is backwards. Because these three are prefix operators (their arguments are the next 1 or 2 expressions to the right), there's no ambiguity between them and thus no need for precedence rules.
> 3 votes

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

Hence, they have the same precedence among eachother if we consider only those three operators. (Note that there can be ambiguity if the unary operators have different position, e.g. $-x^2$, this could mean either $(-x)^2$ or $-(x^2)$ if there was no precendence between $^2$ and $-$.)
> 17 votes

---
Tags: logic, first-order-logic, notation
---


title: Why use heap over red-black tree?

text:
# Question
Title: Why use heap over red-black tree?
Heap supports insert operation in $O(\log n)$ time. And while heap supports remove min/max in $O(\log n)$ time, to remove any element (non min/max) heap takes $O(n)$ time.

However, red-black tree supports insert/remove both in $O(\log n)$ time. We can just remove the first/last element in a red-black tree to remove min/max in $O(\log n)$ time.

I do understand that heaps are used specifically to remove the min/max, but it seems like red-black trees can do what heaps can do but just faster/equal.

Is there any distinctive advantage to using heaps over red-black trees?

# Answer
**Its about pragmatic efficiency.**

The big-O notation tends to simplify many aspects of the machine that the algorithm is executing on. It leaves out the constant multipliers, and constant additions. It doesn't address that even those operations take variable amounts of time. Nor does it address the fact that implementations do not have an infinite/very very large N, but instead operate over particular ranges of N.

**Heaps**

A binary heap can be allocated as a single block of memory if the size of N is known. Even if not known a simple reallocation strategy of doubling the allocation is very efficient. Alternately the blocks can be designed to fit within a memory page having a well-known capacity, and then assembled into balanced block trees.

This has several advantages:

* Keeping the data-structure dense and co-located decreases the likely-hood of a cache miss at the processor level, or a page miss at the memory level - both slow overall execution.
* Organising the tree to follow a predictable memory addressing pattern permits the index to be calculated within the processor and does not require a memory load.
* By minimising the need to reserve memory, memory management book keeping overheads are reduced.

And a few flaws:

* A dense structure incurs an all or nothing memory overhead. An entire page/block must be allocated for even a heap of a single element.
* Modification necessitates element copying - which may not be cheap. A complex object may have internal bookkeeping that is memory location dependent, and must be updated when moved/copied.
* If the capacity of the heap is exceeded a costly re/allocation operation must be performed.

**Trees**

Conversely a tree is generally constructed of nodes which are individually small in size and the nodes are linked via memory addresses. Removing a node is as simple as redirecting the pointers around the removed node, notifying the memory book keeper that it is no longer needed, and then applying a re-balancing operation that adjusts those addresses to achieve a balanced tree.

This has its advantages:

* The tree has exactly the capacity for what is held.
* The tree can be allocated in highly fragmented memory spaces.
* No elements are copied when modifying the tree (excluding creating the node itself).
* Memory bookkeeping is paid as needed.

But has its disadvantages:

* Each node must at least identify its two children, and other book keeping state. Usually `3*sizeof(pointer)`.
* Tree traversal requires memory access to read the location, then another memory access to access the next node.
* Tree nodes are allocated sparsely increasing the chance of a cache-miss, or a page-miss
* Much more memory bookkeeping is required.

**Simplifications**

Note that I have simplified this significantly, and alternate implementation choices could be made:

* I could have used block allocation for the tree, forcing the elements of many nodes other than the one being manipulated to be copied around, while simplifying the rebalancing of the tree, and omitting storage/modification of node addresses.
* I could have used single element nodes for the heap, sacrificing memory density for minimal element copying.

These would have changed the trade-offs and the total cost of each. In a given context these changes would pay dividends, but outside of that context they hobble the use case with unnecessary work.

**Specification**

What is most efficient is situational. Thus it is usually best to specify the exact operations needed, and allow implementations to provide that operation in the most contextually efficient manner it can.

So as before if the operation is over expensive to copy objects, I probably would use a red-black tree to offer Heap operations, or some other similar low-copy data-structure.

Conversely if the data in the heap were single bytes, the block encoded binary heap is a clear winner: `N * (1byte + 3*ptrsize bytes) vs. Nbytes`.
> 15 votes

---
Tags: algorithms, data-structures, heaps, red-black-trees
---