Proof of the lower bounds of time of algorithm working I have asked this question on math.stackexchange already: https://math.stackexchange.com/questions/515920/lower-bounds-on-the-running-time
There are some problems, when there is non-trivial lower bound for working time of algorithm(that solve this problem): sorting, copying words on Turing machine...
What are the modern methods for proof lower bounds of time working do you know? Can you give a reference? Thank you!
 A: Alexey, there is no general pattern that would work in many cases. If one could reliably compute a lower bound one would prove $P\neq NP$ just by computing the lower bound on any of the known $NP$-hard problems.
That said, the lower bound on sorting or $N$ possibly different elements can be computed rather easily by this method: compute the size of the configuration space of all possible solutions and take a logarithm. The reason why the result is a lower bound is that every algorithmic decision cuts the configuration space $S(N)$ of all possible solutions into two subspaces, and in order to cut down to one solution starting from the initial space of $|S(N)|$ possibilities on has to make $log(|S(N)|)$ decision.
In case of sorting the configuration space is all possible order of $N$ inputs, the size of which is $N!$, so the above method gives a lower bound $log(N!)$. Now use Stirling formula $N! \approx (N/e)^N\sqrt{2\pi N}$ to prove the lower bound $N\cdot log(N)$:
$log((N/e)^N\sqrt{2\pi N})=log((2^{log(N)\cdot N}\cdot e^{-N}\cdot\sqrt{2\pi} ) = N\cdot log(N) - O(N) \approx N\cdot log(N)$
Notice that the above bound is wrong when the number of diffrent elements is bound: the configuration space for sorting $N$ elements from $K=const$ possible choices is smaller than $N!$. This is why radix sort can be faster than the above bound.
