# Tag Info

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