0
$\begingroup$

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

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.
$\endgroup$
3
  • $\begingroup$ 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... $\endgroup$
    – D.W.
    Commented Dec 8, 2013 at 22:24
  • 4
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Dec 8, 2013 at 22:25
  • $\begingroup$ Yes, that's correct. It's also possible to go further: $f\cdot 2^{O(f)} = 2^{O(f)+\log f} = 2^{O(f)}$. $\endgroup$ Commented Dec 9, 2013 at 0:31

1 Answer 1

1
$\begingroup$

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))}$$

which is somewhat cleaner.

$\endgroup$
2
  • $\begingroup$ The problem is that the last "$=$" is not defined (formally). There is a relevant answer here. $\endgroup$
    – Parham
    Commented Dec 8, 2013 at 22:04
  • 1
    $\begingroup$ Indeed, this is the old discussion about the flaws of the Landau notation, e.g. here $\endgroup$
    – Shaull
    Commented Dec 8, 2013 at 22:53

Not the answer you're looking for? Browse other questions tagged or ask your own question.