32

The solution is wrong. Demuth [1; via 2, sec. 5.3.1] shows that five values can be sorted using only seven comparisons, i.e. that the "information theoretic" lower bound is tight in this instance. The answer is a method tailored to $n=5$, not a general algorithm. It's also not very nice. This is the outline: Sort the first two pairs. Order the pairs w.r.t....


22

This is a classical result of Winograd: On multiplication of 2x2 matrices. Strassen showed that the exponent of matrix multiplication is the same as the exponent of the tensor rank of matrix multiplication tensors: the algebraic complexity of $n\times n$ matrix multiplication is $O(n^\alpha)$ iff the tensor rank of $\langle n,n,n \rangle$ (the matrix ...


19

We can absolutely prove such things. Many problems have trivial lower bounds, such as that finding the minimum of a set of $n$ numbers (that are not sorted/structured in any way) takes at least $\Omega(n)$ time. The proof for this is simple: a hypothetical algorithm that runs in $o(n)$ time can not examine all of the numbers in the input. So if we ran the ...


16

If you want to multiply two matrices $A$ and $B$ then observe that $$\begin{pmatrix}I_n&A&\\&I_n&B\\&&I_n\end{pmatrix}^{-1}= \begin{pmatrix}I_n&-A&AB\\&I_n&-B\\&&I_n\end{pmatrix}$$ which gives you $AB$ in the top-right block. It follows that inversion is at least hard as multiplication. EDIT: I had misread the ...


14

Yes, it's possible. The classic example is the fact that any comparison-based sorting algorithm requires $\Omega(n\log n)$ comparisons to sort a list of length $n$. However, lower bounds seem to be much harder to prove than upper bounds. To prove that there's a sorting algorithm that requires $O(n\log n)$ comparisons, you just need to exhibit such an ...


13

This is an open problem. Possibly some weak form of 3SUM-hardness could be proved by adapting a result from Mihai Pătrașcu's STOC 2010 paper "Towards Polynomial Lower Bounds for Dynamic Problems". First, let me define a sequence of closely related problems. The input to each problem is a sorted array $A[1..n]$ of distinct integers. 3SUM: Are there ...


11

The standard way to prove things like this is to show that $\Theta(n)$ bits of information must cross at least $\Theta(n)$ points. That is, if you're reversing it "in place", the first third of the bits must cross all $n/3$ middle cells and end up in the last $n/3$ cells. Since the head moves $O(1)$ bits a distance at most $1$ cell each step, this requires ...


10

Lower bounds are of great interest and an active topic of research. However, we tend to be interested in lower bounds for problems and upper bounds for algorithms. An upper bound for an algorithm is a performance guarantee: the algorithm will not use more than such-and-such an amount of memory or processing steps when run on an input of a particular size. ...


10

I did a quick read over the paper you linked. Based on the ideas given in that paper, here's a simple data structure that obtains an $O(\frac{\log n}{\log\log n})$ time bound on each operation. You mentioned in your question that you can use balanced, augmented trees to speed this up. In particular, if you have a binary tree and augment each node with the ...


9

Although this is not tight, I can offer lower and upper bounds of $1/4$ and $3/4$ on the worst case ratio between guillotine cuts and general cuts. Let us start with the upper bound and assume we are given a square piece of glass with a side length of $2$. Furthermore, we have exactly one buyer who is interested in rectangular glass sheets of width $1-\...


9

As Pål GD mentions in his comment, the proof is actually very simple: there are $2^{2^n}$ functions, but only $C_S = S^{O(S)}$ circuits of size at most $S \geq n$. The exact constant in the exponent depends on the exact definition of a circuit. Getting the best exponent requires some rather intricate arguments, together with the assumption $S = \omega(n)$. ...


9

Solving intersection Non-Emptiness for 2 DFA's: It essentially just becomes a reachability problem for the product DFA. Roughly, we can solve it deterministically in $O(n^2)$ time using $O(n^2)$ space. Or, we can solve it non-deterministically with $O(\log(n))$ space. By Savitch's Theorem, we can also solve it deterministically in $2^{O(\log^2(n))}$ time ...


9

The relevant result is known as Turán's theorem. It states that if a graph has less than (roughly) $n(n-1)/(2r)$ edges then it has an independent set of size $r+1$, and this is tight.


8

There is an invariant that each move can only increase the number in your longest increasing subsequence by at most 1. If your initial array has $k$ values in its longest increasing subsequence, you need $n-k$ moves at least to get it sorted. This shows $n-k$ moves is necessary.


8

Consider the following set of $n$ orders, which I give for $n = 6$: $$ 123456 \\ 213456 \\ 132456 \\ 124356 \\ 123546 \\ 123465 $$ Hopefully the generalization to arbitrary $n$ is clear. If you never compare $i$ and $i+1$ then you cannot tell apart permutation $1$ from permutation $i+1$. This means that you need at least $n-1$ comparisons (this is not an ...


8

No, a lower bound means that somebody has proved that anything smaller than 53 is impossible. That doesn't mean that a 53-gate network is known or even necessarily possible; just that there cannot be a smaller one than that.


7

Finding an envy-free cake-cutting requires $\Omega(n^2)$ queries. However, this does not directly answer your question as the computational model is different than a Turing machine. By the way, currently the quickest known algorithm for this problem requires $n^{n^{n^{n^{n^{n}}}}}$ queries, so there is a huge gap from the lower bound - probably one of the ...


7

Given $n$ integer points $p_1,\ldots,p_n$, not necessarily distinct, consider the set of points $2np_1+1,2np_2+2,\ldots,2np_n+n$. The new points are distinct by construction, and the minimal distance is smaller than $n$ iff the original points were not distinct. So an algorithm for your problem can be used to solve element distinctness.


7

This has been proved by Muller as early as 1956. Here is the construction. Let $k$ be a parameter. We first compute all possible functions on the first $k$ inputs in size $O(2^{2^k})$ (see below). We then construct a decision tree for the other $n-k$ variables, connecting it to the correct function on the remaining variables. This takes $O(2^{n-k})$ (see ...


7

No. There are no known polynomial bounds. The best lower bounds known are merely linear. As described here, the situation for circuits at least is "quite depressing": there are no known lower bounds that are better than $\sim 4n$. That's the case even when you pick the problem. There is no explicitly known problem where we can prove a lower bound better ...


7

This answer assumes that your question is about computing the sorted order of $\{ x_i + x_j : 1 \leq i,j \leq n \}$ given a list $x_1,\ldots,x_n$. This problem is a special case of $X+Y$ sorting. According to Wikipedia, no algorithm whose complexity is better than $O(n^2\log n)$ is known for this problem. The decision tree complexity, however, is only $O(n^...


7

We assume the comparison model in the lower bound of the element uniqueness problem. That is, the key operations are to compare elements. In particular, hashing is not allowed.


7

You can find the result at: S.Winograd, On multiplication of 2×2 matrices, Linear Algebra and Appl. 4 (1971), 381–388, MR0297115 (45:6173).


7

You can use color-coding, a celebrated technique due to Alon, Yuster and Zwick.


6

These are some of the best time and space bounds known. In this area the research has gone to the direction of giving bounds in both time and space. My understanding is that superlinear time bounds without a space constraint are not known. Time-Space Lower Bounds for Satisfiability Lance Fortnow, Richard Lipton, Dieter van Melkebeek We establish the first ...


6

For the first part, as the comments suggest - observe that there are $k!^n$ possible permutations for the inputs - indeed, every array has $k!$ permutations, and there are $n$ arrays, so you have $k!$ options for the first array, $k!$ for the second, and so on. So the height of a decision tree is $$\log (k!^n)=n\log (k!)\in \theta(nk\log k)$$ So you need ...


6

You can codify your method in the following lemma. Lemma. If $f(n)/g(n) \rightarrow C$, where $C > 0$, then $f(n) = \Theta(g(n))$. The proof is the same as the one you gave. After you prove this lemma once and for all, you can use it forever. That's actually a good way of verifying $f(n) = \Theta(g(n))$. Note that the converse to the lemma isn't true. ...


6

Any algorithm would need $\Omega(\log n)$ queries. To see this, define $f(k)$ to be the number of queries needed for deciding whether an element $x$ appears at least $a$ times in a sorted array $A$. We assume that $x$ appears in $A[m],A[m+1],\dots,A[M]$, and that $k\triangleq\min\{a, m-1, n-M\}$. Notice that in these notations we are looking to bound $f(\...


6

No. You can't do better than $\Theta(n^2)$ in the worst case. Consider an arrangement of points where every pair of points are at distance $1$ from each other. (This is a possible configuration.) Then you can't do better than to examine every edge. In particular, if there is any edge you have not examined, then an adversary could choose the length of ...


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