How can I prove that n . log n is a time constructible function?

Question

I want to show that $$n\log(n)$$ is a time constructible function. Can anyone help, how can I prove it?

Thanks in advance.

Answer 1

A function $f: \mathbb{N} \rightarrow \mathbb{N}$ is time-constructible if there exists a Turing machine that can compute $f(n)$ from $n$ in $O(f(n))$ steps.

One way of computing $n \log n$ is to simulate an algorithm whose worst-case time complexity is $O(n \log n)$ on an appropriately generated input and count the steps during the simulation.

An example of an algorithm with this worst-case time complexity is mergesort; it will use $O(n \log n)$ steps on an input that is "alternately sorted".

To use $O(n \log n)$ steps, run mergesort with the input list $[0,2,1,4,3, \ldots, n]$.