# Theory of Complexity – Prove the Existence of a Language \$ L in DTIME (n ^ { log n}) \$ that is not in \$ Avg-P \$

I have trouble with the following question:

To define $$P-Avg$$ the class of all languages $$L$$ for which there is a polynomial Turing machine $$M$$ as for each $$n$$, for all except $$frac {2 ^ n} {n}$$ of $$2 ^ n$$ length ropes $$n$$, $$M$$ gives the correct answer as to whether $$x in L$$ or not.
Prove that there is $$L in DTIME (n ^ { log n})$$ which is not in $$P-Avg$$.

My attempt: I thought about using diagonalization. First, we list all Turing machines $$M_1, M_2, M_3, …$$. We now define the following MT: for the input $$x$$ length $$n$$simulate $$M_n$$ entrance $$x$$ for $$n ^ { log n-1}$$ not. If the simulation stops, answer the opposite. Otherwise, reject. Now, let's define $$L (T) = L$$. It's easy to see $$L in DTIME (n ^ { log n})$$. Suppose now that the contradiction $$L in P Avg$$. So there is $$M_i$$ who gives the right answer to whether $$x in L$$ for all except $$frac {2 ^ i} {i}$$ of $$2 ^ i$$ length ropes $$i$$. But because $$T$$ simulated $$M_i$$ and responds on the contrary, it is a contradiction.

The problem: I did not find a way to ensure that the simulation actually stops $$M_i$$and responds on the contrary as wanted. Any ideas how can I solve this solution / solve in another way?