0

It's been a while since I had to deal with some sort of asymptotic analysis so I am a bit rusty and trying to get the basics back together. Since I don't really know where to look for these things, I ask you: is the following correct?

Let $p_i,q_i \in \mathbb R$ with $0<p_i<q_i$. Let $a_i, b_i\in \mathbb R$ with $1<a_i<b_i$. Then we have

$ \log(n) \ll n^{p_1} \ll n^{q_1} \ll a_2^{n^{p_2}} \ll b_2^{n^{p_2}} \ll a_3^{n^{{q_2}}} \ll n! \ll n^n$

And: would you add anything to that list? (Take this as a "soft question". I think it might be possible, with suitable products with logarithms, to add an infinite sequence at every step, but I mean "atomic sequences", whatever that may mean.)

Let me clarify on the use of the $\ll$ symbol. I write $a_n\ll b_n$ if $\lim_n \frac{b_n}{a_n}=\infty$.

user46225
  • 731
  • 4
  • 11
  • Ok, I think I wrote what I meant to write now. Sorry for the confusing notation but I couldn't think of anything better so as to put everything in a single sequence. – user46225 Dec 01 '14 at 17:43
  • Are you using the $\ll$ symbol to mean $P(n)\ll Q(n)$ if there is an absolute constant $C$ such that $P(n)\leq CQ(n)$ or that $P(n)/Q(n)\leq C$ for $n\geq N$ for some $N$ sufficiently large; or is it notation for one quantity being "much smaller" than the other? Also, are the numbers $p_{j},q_{j}$ and $a_{j},b_{j}$ arbitrary pairs with no relation between the indices? – Sargera Dec 01 '14 at 17:46
  • @TaylorMartin: I've edited to clarify. – user46225 Dec 01 '14 at 17:48
  • 1
    If $q_2 > 1$, then $a_3^{n^{q_2}}$ grows faster than $n^n$ (take logarithms to see that). – Daniel Fischer Dec 01 '14 at 17:48
  • @DanielFischer: Ah shoot. What if we restrict to roots, i.e. $q_2\leq 1$? – user46225 Dec 01 '14 at 17:49
  • If $q \leqslant 1$, then $a^{n^q} \ll n!$ all right. – Daniel Fischer Dec 01 '14 at 17:51
  • @Daniel: So, the sequence as it is written works for $q_2\leq 1$, and for any $q_2$ provided we delete the last two $\ll$, am I correct? Thank you for your comments. – user46225 Dec 01 '14 at 17:52
  • 1
    Right. $n!$ and $n^n$ sit between $a^n$ (with $a > 1$) and $b^{n^{1+\varepsilon}}$ (with $b > 1$) for every $\varepsilon > 0$. – Daniel Fischer Dec 01 '14 at 17:55
  • 1
    Check out this thread. I think it is a good place to start. :-) http://math.stackexchange.com/questions/672692/list-of-calculation-rules-for-asymptotic-notation/745188#745188 – ml0105 Dec 01 '14 at 18:05
  • @DanielFischer: sorry to ping you here about something else, but I think you might have something nice to say on this new question of mine: http://math.stackexchange.com/questions/1048852/when-can-you-replace-by-an-equivalent-in-a-sum-or-inside-some-given-function – user46225 Dec 02 '14 at 21:18

0 Answers0