Consider the following algorithm (a variant of Levin's algorithm):
> Run the first $n$ algorithms in parallel. Additionally, run in parallel a brute-force algorithm that tries all possible solutions one by one. (Run all algorithms with the same speed.)

> Stop when one of the algorithms finds a solution.

Consider two cases (given an input $x$ of length $n$):

 - $Q$ is one of the first $n$ algorithms. Then the running time is $O(n \cdot t^M_Q(n)) \cdot \mathrm{poly}(n)$.

 - $Q$ is not one of the first $n$ algorithms (thus $n < 2^{|Q|}$). Then the running time is bounded by the running time of the brute-force algorithm. We have that the running time is  $2^{n^{O(1)}} = 2^{2^{O(|Q|)}}$.

We have 
$$t^M_A(n) \leq \mathrm{poly}(n) \cdot t^M_Q(n)  + 2^{2^{O(|Q|)}}.$$