Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [asymptotics]

For questions involving asymptotic analysis, including function growth, Big-$O$, Big-$\Omega$ and Big-$\Theta$ notations.

Questions involving asymptotic analysis, including function growth, Big-$O$, Big-$\Omega$ and Big-$\Theta$ notations.

  • $f(x) = O(g(x))$ as $x \to \infty$ is used to mean that for sufficiently large values of $x$, we have $|f(x)| \leq A g(x)$ for some constant $A$.

  • $f(x)=\Omega(g(x))$ is equivalent to saying that $g(x)=O(f(x))$.

  • $f(x)=\Theta(g(x))$ is used to mean that $f(x)=O(g(x))$ and that $f(x)=\Omega(g(x))$.

9469 questions
6
votes
3 answers

Does $n n^{1/n} =O(n)$?

I was asked does $n n^{1/n} =O(n)$ ? I can see that the left hand side is always bigger than $n$ but how would you prove the equality is false?
Enid
  • 71
6
votes
3 answers

Are there any divergent series that approximate to O(log log log n)?

$$1 + {1 \over 2} + {1 \over 3} + {1 \over 4} + \cdots \sim O(\log n)$$ $${1 \over 2} + {1 \over 3} + {1 \over 5} + {1 \over 7} + \cdots \sim O(\log\log n)$$ $$\text{???} \sim O(\log\log\log n)$$ Are there any divergent series (each of terms is…
Antithesis
  • 73
6
votes
1 answer

How can stationary phase approx lead to log terms?

In these lecture notes (http://www.math.ucla.edu/~tao/247b.1.07w/notes8.pdf, section 3), Terence Tao approximates the following integral for large $\lambda$ using the stationary phase method: $\begin{align} I_{a,\phi}(\lambda) &:=…
marlow
  • 793
6
votes
2 answers

Big-O Notation and Asymptotics

I realize that this is not a typical programing question but its still related. If anyone could help me out I would really appreciate it because I have a midterm coming up and this is the part that I don't understand. This is not a homework problem…
user7538
6
votes
2 answers

Asymptotics of $\sum\limits_{n=2}^\infty \frac{x^n}{(\log n) n!}$ as $x\to\infty$

I believe, based on numerical evidence, that $$\sum_{n=2}^\infty \frac{x^n}{(\log n) n!} \sim \frac{\exp(x)}{\log(x)}$$ as $x\to\infty$. However, I am not sure how to prove this. What would be a good way to approach this problem?
Eric M. Schmidt
  • 3,717
6
votes
1 answer

Asymptotic behavior of $\sum\limits_{k=2}^{m}\frac{1}{\ln(k!)}$

The task is to find asymptotic behavior of sum: $$\sum\limits_{k=2}^{m}\frac{1}{\ln(k!)}$$ when $m\to\infty$. Any help with solving this one?
aam
  • 163
6
votes
1 answer

Asymptotics for Bell number

Concrete Mathematics EXERCISE 9.46 Show that the Bell number $\varpi_n=e^{-1}\sum_{k\ge0}k^n/k!$ of exercise 7.15 is asymptotically equal to \[ m(n)^ne^{m(n)-n-1/2}/\sqrt{\ln n} \] where $m(n)\ln m(n) = n-\frac12$, and estimate the relative…
Yai0Phah
  • 9,733
6
votes
4 answers

Which of $\log{\sqrt{n\log{n}}}$ and $\sqrt{\log{n}}$ grows faster?

Which of the following functions grows faster: $\log{\sqrt{n\log{n}}}$ or $\sqrt{\log{n}}$? I feel the second one should be the answer, but I find it difficult to prove as the derivatives get very complex. Does anyone know any idea?
user24175
  • 199
6
votes
0 answers

Comparing asymptotic forms of series

I've run into some asymptotic analysis in research here and there and largely it feels pretty magical to me. My research has led me to consider the following question which I haven't the slightest idea how to address: If we have two series $f(x) =…
Cameron Williams
  • 29,432
6
votes
2 answers

If $f(n)$ is $O(g(n))$ and $g(n)$ is $O(f(n))$, is $f(n) = g(n)$?

Question: If $f(n)$ is $O(g(n))$ and $g(n)$ is $O(f(n))$, is $f(n) = g(n)$? I'm studying for a discrete mathematics test, and I'm not sure if this is true or false. Since Big-OH ignores constant multiples, wouldn't $f(n) = c\, g(n)$?
ellman121
  • 163
6
votes
1 answer

Asymptotic behavior of $\sum_{k=1}^{n}\left(1-p^{k}\right)^{n-k}$

I'm looking for pointers as to how to evaluate the asymptotic behavior of $\sum_{k=1}^{n}\left(1-p^{k}\right)^{n-k}$ for large $n$ where $0
PeterR
  • 835
5
votes
2 answers

function asymptotic where $f(x) = \frac{a + O(\frac{1}{\sqrt{x}})}{b + O(\frac{1}{\sqrt{x}})}$

If $a$ and $b$ are positive real numbers, and if $f(x)$ has the following asymptotic property $f(x) = \frac{a + O(\frac{1}{\sqrt{x}})}{b + O(\frac{1}{\sqrt{x}})}$ then is the following true? $f(x) = \frac{a}{b} + O(\frac{1}{\sqrt{x}})$ This might…
lolol
5
votes
1 answer

Asymptotics of $\sum_{i=1}^{n^2 - 1} \frac{i^2}{[\frac{n^3}{3}]^2}$

I need to somehow figure out what happens with the following sum: $$\sum_{i=1}^{n^2 - 1} \frac{i^2}{[\frac{n^3}{3}]^2}$$ when $n \rightarrow \infty$. Should it be zero? Should it be a constant? If I try and guess that sum of squares from $1$ to $n$…
wh1t3cat1k
  • 945
5
votes
2 answers

Asymptotic expansion of the integral $\int_2^\infty \frac{x^t}{\ln(t)} dt$ for $x \to 1$

If we define $$F(x)=\int\limits_{2}^{\infty}\frac{x^t}{\ln(t)}dt$$ I'm interested in the asymptotic expasion of $F$ as $x$ approaches 1. I'm pretty sure this integral has no elementary anti-derivative so I can't venture down that route. I can't…
Elie Bergman
  • 3,917
5
votes
2 answers

What's the asymptotic lower bound of the sum $\frac 3 2 + \sum_{k=3}^{n} \frac{n!}{k(n-k)!n^k}$?

The sum is: $$ S = 1 + 1/2 + \frac {(n-1)(n-2)} {3n^2} + \frac {(n-1)(n-2)(n-3)} {4n^3} + \ldots + \frac {(n-1)!} {n \times n^{n-1}}$$ $$= \frac 3 2 + \sum_{k=3}^{n} \frac{n!}{k(n-k)!n^k} $$ Can we get an asymptotic lower bound of $S$? I guess…
NonalcoholicBeer
  • 7,211
1 2
3
…
74 75