I having some trouble tackling an assignment. We're asked to prove that there exists a recursive language that's not decidable by a Turing machine in $O(n)$ time for inputs of length $n$. We're supposed to do so using diagonalization.
Here's what I have so far:
Assume that for each recursive language $L$, there exists a TM that decides $L$ in $O(n)$ time for each input of length $n$.
We build a TM, $U$, that for each input, $w$, $U$ interprets $w$ as $ w = 1^k0\langle M\rangle$, where $\langle M\rangle$ is an encoding of a TM for language recognition. It then runs $M$ on $w$, and if $M$ halts, then $U$ outputs the opposite of $M$'s output. Therefore,$ U$ must perform at least $k$ steps in order to extract the encoding of $M$ from the input. I'm still not sure how to continue from here.