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 ...


17

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 ...


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

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 ...


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.


8

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

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

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

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 ...


6

No such non-trivial bound can be obtained. Consider the language $L_n = \{ 0^{kn} : k \in \mathbb{N}\}$. Any NFA for $L_n$ needs at least $n$ states, but it can be generated by a context-free grammar with only one non-terminal: $S\to 0^nS|\epsilon$.


6

The lower bound for an problem states that "no algorithm can do better than this". In your case, it means that no sorting network for 16 inputs can have fewer than 53 gates. Sometimes there can be confusion between the reader and writer regarding whether a lower bound is tight or not. A tight lower bound states, "no algorithm can do better than this, and ...


6

Yes: Checking that a string is a palindrome takes $\Omega(n^2)$ on a single tape Turing machine. In general the time hierachy theorem implies that there are such problems for most reasonable functions. For RAM, edit distance can't be solved in $O(n^{2-\epsilon})$ for $\epsilon > 0$ unless the strong exponential time hypothesis is false.


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