I have already asked a similar question where the tilde notation was used (and context can be taken from there). Now I think that tilde is not the correct symbol to go between these two functions since tilde is defined as $\lim\limits_{n\to \infty}\dfrac{f(n)}{g(n)} = 1$, but the functions in question actually tend to $\frac{1}{\sqrt{5}}$, though I might be wrong.

So in terms of asymptotic analysis can anyone help me understand in which relation are these two functions exactly?

  • $\begingroup$ You could use Big Theta ($\Theta$). $\endgroup$ Mar 20 '19 at 10:04

The usual approach is to write $F_m\in\Theta(\phi^m)$ or, in an abuse of notation, $F_m=\Theta(\phi^m)$. See here for some other common relations; $\mathcal{O}$ and $\Omega$, in particular, can be accurately used here.

  • $\begingroup$ Can one say that $F_m\sim\phi^m$ is not correct or it can be somehow used? $\endgroup$ Mar 20 '19 at 10:07
  • 1
    $\begingroup$ @MichaelMunta It is incorrect, because it implies a ratio of limit $1$. I can understand someone saying, "let's redefine it to not care about the exact limit", but we already have notation for that weaker statement; it's worth keeping the strong meaning of $\sim$ for when we'd like to say it. $\endgroup$
    – J.G.
    Mar 20 '19 at 10:10
  • $\begingroup$ Isn't big O just giving the upper bound on the function? $\endgroup$ Mar 25 '19 at 10:30
  • $\begingroup$ @MichaelMunta My mistake! I've edited my answer. $\endgroup$
    – J.G.
    Mar 25 '19 at 10:31
  • $\begingroup$ This might be a stupid question, but on the link you have provided where all notations are listed there is a formal definition column. I am wondering whether the constants there like $k, n_0$ etc need to be integers or they can be any real number? $\endgroup$ Mar 27 '19 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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