# Tag Info

8

This can be modelled as a Max-Flow problem. As a preprocessing step, make sure that the number of games is equal to the sum of the number of wins (if not, you know something is wrong). Let $G$ be a set of vertices corresponding to the games played, and $P$ a set of vertices corresponding to the players. Let $s$ and $t$ denote two additional vertices (...

4

It's true. There are positive constants $c_1$, $c_2$, $c_3$ and $c_4$ such that, for all large enough $n$, $$c_1n^4 \leq x\leq c_2 n^4 \quad\text{and}\quad c_3n^2\leq y\leq c_4n^2\,.$$ Therefore, $$\frac{c_1}{c_4}n^2 \leq \frac{x}{y}\leq \frac{c_2}{c_3} n^2\,,$$ i.e., $x/y=\Theta(n^2)$. By the way, in your argument, you say that $x$ and $y$ are ...

3

First, $|V|$ is the number of vertices and $|E|$ is the number of edges. The point is that if a graph is connected it must have at least $|V|-1$ edges. Therefore, $|V|\leq |E|+1$, so $$|V|\log|V| + |E|\log|V| \leq 2(|E|+1)\log|V|\leq 3|E|\log |V|\,.$$ Writing $|V|=O(|E|)$ is something of an abuse of notation. $O(\cdot)$ is an asymptotic statement about ...

3

You're mistaken. The analysis of the Karatsuba algorithm takes addition and subtraction into account. If you analyze your pseudo-code, you can see that you have exactly 3 recursive function calls with arguments of size $n/2$, and all other operations like addition, subtraction, extracting the higher and lower bits, ..., run in $O(n)$. Therefore you get ...

2

Let's say you have n = 100, $a_1 = 50$, $a_{100} = 100$, and $a_{50} = 73$. You would then know that the range from $a_1$ to $a_{50}$ contains all numbers from 50 to 73, and maybe some others, and the range $a_{50}$ to $a_{100}$ contains all numbers from 73 to 100, and maybe some others. I think binary search will actually work, if the number you are ...

2

I hope I'm not misunderstanding you, but keep in mind that you don't just have to find the node you want to get rid of. You also have to replace it with another node to still have an intact tree afterward. For it to then still be a binary tree that node needs to be closest to the root in value. The worst case will turn out to be that all nodes have two ...

1

If you approximate this as an integral of the second for loop you get, substituting $k=(n-i)$: $$I_n = \int_1^n \frac{n+(n-k)^2-(n-k)+1}{k} dk = \int_1^n 1+\frac{(n-k)^2+1}{k} dk$$ according to WA, the corresponding antiderivative is of the indefinite integral is: $$(n^2+1)log(k) + \frac{1}{2}k(k-4n+2) +C$$ Thus, evaluating at $k=1$ and $n$ we get: ...

1

It's true that on page 73, the author defines the abstract functions $Predecessor(D, k)$ and $Successor(D, k)$, which find the predecessor and successor of a given key. But the chart on page 74 lists the interfaces as $Predecessor(L, x)$ and $Successor(L, x)$, which find the predecessor and successor of a given entry index. Clearly this is O(1) for a ...

1

(Deterministic) TMs with a single tape can recognize palindromes in time $O(n^2)$. It has been proven that this time bound is optimal (see, e.g., this paper). Also, the time hierarchy theorems give you an endless supply of such examples (though they are not natural problems, of course).

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