# Tag Info

0

With a hint from Steven Stadnicki, an example was found: $g(n)=1/n$, $f(n)=2^{n^3}$. Indeed, $$f(n-g(n))=2^{(n-1/n)^3} = 2^{n^3-3n+3/n-1/n^3} =\Theta(2^{n^3-3n})=o(2^{n^3})$$

0

Consider the game played with a specified finite list $C$ of cities, where $|C|=N$. Then $C = \bigcup_{i,j \in \{a"\ldotsz"\}} C_{ij}$ where $C_{ij}$ is the subset of $C$ consisting of cities whose name starts with $i$ and ends with $j$. A state of the game conists of nonnegative integers $n_{ij}$ (the number of cities in $C_{ij}$ that have not yet ...

1

This is covered in the wiki article on the power diagram.

2

Take the intersection of $x_0^2+...+x_n^2=n^2+n$ and $x_0+...+x_n=0$. This is an $n-1$-dimensional surface of an $n$-dimensional sphere. It contains the points $(n,-1,-1,-1,...,-1)$, $(-1,n,-1,...,-1)$ and so on. For any point on the sphere, at least one coordinate is positive, so at least one of the dot products with these points is positive. So $n+1$ ...

1

Another approach: $$\frac{\color{red}n\log(2^n\log n^2)}{n^{\color{red}2}}=\frac{n\log2+\log2+\log\log n}n=\log 2+2\frac{\log2+\log\log n}n\xrightarrow[n\to\infty]{}\log2$$

1

$n\log(2^n\log(n^2))=n\log(2^n)+n\log\log(n^2)=n^2\log(2)+n\log(2)+n\log\log n$ Note that the last two are negligible compared to $n^2\log 2$ as $n$ grows large. We can choose $\log 2\le k\le \log 2+\frac{\log 2}{e}$ for $\frac{n^2\log(2)+n\log(2)+n\log\log n}{n^2}=k$ for sufficiently large $n$, so $n\log(2^n\log(n^2))=O(n^2)$

1

$$n\log(2^n\log(n^2)) = n\log(2^n) + n\log\log(n^2) = n^2\log(2) + n\log(2\log n)$$ For simplicity I assume that $\log = \log_2$. Then this becomes $$n^2 + n + n\log\log n$$ Is this $O(n^2)$?

0

Neither of these expressions can be simplified further.

0

There are a few observations one can make: Graph $T$ consists of three components (allowing the possibility of one-vertex components) which are not connected to each other. In order to turn it into a spanning tree, we need to add two edges, each of them joining one pair of components. Total weight of the spanning tree is the weight of $T$ (which is beyond ...

0

Here's the approach I am going with: For generating puzzles, I use specific numbers of swaps - lesser for easier levels and more for harder levels. For evaluating a given puzzle (to enable sharing of puzzles), I will first solve the puzzle, and then use the Levenshtein distance - to determine distance between the puzzle and the solution, and use that as ...

3

Your second approach is good. The minimum number of swaps is a measure of complexity in the symmetric group that is frequently used, and correlates directly with gameplay length.

0

First, let's consider a simpler problem; Alice and Bob are both given $n$-bit binary strings, and they must decide whether the two strings are the same. Let's call this problem $EQ_n$. It's a classical result in communication complexity that $D(EQ_n) \geq \Omega(n)$ (in fact, $D(EQ_n) = n$); you can see a proof here: ...

0

This is incorrect. If $L$ were in $RP$, then there would be a deterministic TM that would accept with probability 2/3 on a correct input and reject with probability 1 on an incorrect input (along with a second input of random bits) in polynomial time. You're correct that $BPP$ gives you the first condition, but $NP$ makes no guarantees about the second. It ...

2

Here's another $O(n^2\log n)$ algorithm, similar to Ross Millikan's but slightly different. Start by sorting the $s_i$'s into increasing order, i.e., assume $s_1\le s_2\le\cdots\le s_n$. This can be done in $O(n\log n)$ steps, so we can assume the $s_i$'s came this way. Given such an ordered sequence, and given any number $S$, straightforward "bisection" ...

1

You can do $O(n^2 \log n)$. Let us work on the same problem without $s_k$, so we are minimizing $|s_i+s_j-l|$ and show an $O(n \log n)$ algorithm. Then you can just loop $k$ from $1$ to $n$ to get $O(n^2 \log n)$. Sort the $s$'s into an array $t_1,t_2\dots t_n$ with $t_1 \lt t_2 \lt \dots t_n$ Now compute $t_1+t_n-l$ If it is positive, you may improve ...

0

Since $k$ is given, the value of $s_k - k$ is also known, so you only need to look through all possible $ij$ pairs; that's $O(n^2)$.

1

The short answer is that adding two numbers by the "elementary school" algorithm has linear complexity. That is, given binary representations F and H of respective lengths $s$ and $t$, the number of steps needed is $O(s+t)$. This should be intuitively clear. After arranging the longer number over the shorter one, starting at the right hand side and ...

0

For all $n\ge 1$ we have \begin{align*} n^3-5n^2+25n-165&\le n^3+5n^2+25n+165\\ &\le n^3+5n^3+25n^3+165n^3\\ &=\ldots\;? \end{align*} This idea generalizes to handle any polynomial. For the second, note that $0<\frac1n<\pi$ for all $n\ge 1$, so $0<\sin\frac1n\le 1$, and therefore $3<3+\sin\frac1n\le 4$.

0

For part 1), you first want to know the definition of big-$O$ notation. This should then just give you the answer. In general, you want to look at the term that has the "most effect". In polynomials, this would be the term with the highest degree. There you have it.

0

I'll just give you some general advice for solving this kind of problem which is probably too long to fit into a comment but isn't an actual complete answer. 1) Learn what the algorithm is supposed to do. I think it might be trying to implement some of this functionality. 2) Every function has assumptions that are made when the function is first called, ...

1

HINT: What is $$\lim_{x\to\infty}\frac{(\ln x)^2}x\;?$$

1

$m > n - 1$ implies that $(n-3) \log(n-3) < (m-2) \log (m-2)$. That is $O(m \log m)$, but not $O(m)$.

0

I'm not sure I understand your question correctly, but if $f$ is primitive recursive, then $H_f$ will likewise be primitive recursive: \begin{align} H_f(\vec x, 0) =& \langle f(\vec x,0) \rangle \\ H_f(\vec x, y+1) =& H_f(\vec x,y) * \langle f(\vec x,y+1) \rangle \end{align} where $\langle\cdots\rangle$ is the function that encodes a ...

2

It is easy for $g$ to exist if you don't require that $g$ hits all indices for a program that computes $g$. In that case we can say, essentially \begin{align}g(n) = &\text{let } x = \text{the source for this program (by any standard quine construction)}\\ &\text{in the index of the program that consists of }n\text{ "skip"s followed by }x ...

1

Take $p=1$ and $k=1$. Consider $A=\{0,3\}$ and $B=\{2,5\}$. $d_0^A=3$ and $d_0^B=2$ $d_2^A=1$ and $d_2^B=3$ $d_3^A=3$ and $d_3^B=1$ $d_5^A=2$ and $d_5^B=3$ So $A'=A$ and $B'=B$, so $A$ becomes $B$ and $B$ becomes $A$, and the algorithm never stops.

Top 50 recent answers are included