# Correctness of asymptotic expression from exact expression [closed]

I have the expression: $$|Q|f(n)|\Gamma|^{f(n)}$$

Here is my solution to convert the above into an asymptotic expression: $|Q| = 2^l$ for some $l\in\mathbb{R}$ $|\Gamma| = 2^k$ for some $k\in\mathbb{R}$

Therefore we have $2^lf(n)(2^k)^{f(n)} = f(n)2^{kf(n)+l} = f(n)2^{O(f(n))}$

1. Is this correct? I just want to verify my understanding of a discussion in Sipser's Theory of Computation text.
• I not sure whether I understand your notation. Do you mean $|Q| \times |f(n)| \times |\Gamma|^{f(n)}$? You seem to be missing some vertical lines. Also what is the definition of $Q$, $f$, and $\Gamma$? Do you really mean "for some", or do you mean "for all"? If $Q$ is a function of $l$, knowing that $|Q|=2^l$ for some $l$ does not tell you anything useful about the asymptotic behavior of $Q$. (If $Q$ is a constant, you might want to say so.) You might want to proof-read your question and edit it to correct these issues...
– D.W.
Commented Dec 8, 2013 at 22:24
• This question appears to be off-topic because questions of the form: "This is the exercises problem, this is my solution. Please grade!" are not a good fit for this site. Please see this related meta discussion. If you want to ask a specific question about a specific part of your attempt, please edit the question accordingly and it may be reopened.
– D.W.
Commented Dec 8, 2013 at 22:25
• Yes, that's correct. It's also possible to go further: $f\cdot 2^{O(f)} = 2^{O(f)+\log f} = 2^{O(f)}$. Commented Dec 9, 2013 at 0:31

What you wrote is correct under the assumption that $|\Gamma|$ and $|Q|$ are constant (which, from the context, is indeed the case), but can be taken a bit further, and can be made more explicit:
For every $x>0$ it holds that $x=2^{\log x}$. Therefore you get
$$f(n)|Q||\Gamma|^{f(n)}=2^{\log f(n)}2^{\log |Q|}2^{f(n)\log |\Gamma|}= 2^{\log f(n)+\log |Q|+f(n)\log |\Gamma|}=2^{O(f(n))}$$
• The problem is that the last "$=$" is not defined (formally). There is a relevant answer here. Commented Dec 8, 2013 at 22:04