Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

New answers tagged

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