New answers tagged lower-bounds
1
This answer uses the convention that the elements of $X$ are $x_1,\ldots,x_n$ (in their original, unsorted order), and similarly the elements of $Y$ are $y_1,\ldots,y_n$. This differs from your convention.
The complexity of this problem in the comparison model (as well as in related models, such as bounded degree algebraic decision trees) is $\Theta(n\log n)...
3
The time hierarchy theorem gives, for every $k$, a function in P with a runtime lower bound of $\Omega(n^k)$. Unfortunately, this is not enough to separate P from NP: to do this, we need a function in NP with a superpolynomial runtime lower bound.
One popular approach for tackling the P vs NP question is via circuits. The best lower bounds for explicit ...
0
A bound function is $n-j-1$. Let us check the conditions one by one:
$n-j-1$ is an integer-value total function of some of the variables. (A function is total if it is defined on all inputs.)
When the loop body is executed, $j$ is increase by one, and so $n-j-1$ is decreased by one.
If $n-j-1 \leq 0$ then $j \geq n-1$ and so $j > n$, hence the loop ...
0
The theoretical lower bound on comparison based sorting is $\log(n!)$.
That is to say that to sort $n$ items using only $<$ or $>$ comparisons it takes at least the base 2 logarithm of $n!$, hence $\log(5!) \approx 6.91$ operations.
Since $5!= 120$ and $2^7= 128$,
using a binary decision tree you can sort 5 items in 7 comparisons.
The tree figures out ...
Top 50 recent answers are included
