Problem: Given an encoding of a Turing machine M and a natural number k as input, find the output of M (given a blank tape) after k steps.
Wikipedia's page on EXPTIME-complete says it takes O(k) time but the page on universal Turing machines says O(k log k) on a multitape machine which only implies a single tape machine might do even worse.
Am I mixing things up? What is the best known bound for the given problem? Is it provably optimal? If not, what is the best bound that probably cannot be beaten?
Thanks for clearing this long standing doubt