Questions involving asymptotic analysis, including growth of functions, Big-O notation, Big-Omega and Big-Theta notations.

learn more… | top users | synonyms (1)

1
vote
1answer
47 views

Showing $n^{\log{n}} = o(2^n)$

I would like to show that $n^{log n} = o(2^n)$. Here is my attempt: I see that $\log{(n^{\log{n}})} = (\log{n})^2,$ and $\log{2^n} = n\log{2}$. I also know that $(\log{n})^2=o(n)$, so that for ...
0
votes
1answer
11 views

Orders of Asymptotes

We know that $\log(X)^n = o(X^\epsilon)$ for all $n,\epsilon>0$. My questions is, is $\log(X)$ the largest function that is smaller than all (small) powers of $X$. That is, can we find a (non-...
1
vote
2answers
46 views

On finding the order of an infinitely small quantity

Given an infinitely small quantity: $$\alpha \left ( x \right )= \tan \left ( x \right )-\sin \left( x \right)$$ as x aproaches $0$, and computing the corresponding asymptotic relationship. What does ...
3
votes
2answers
68 views

Can we give a bound on any associative function?

We say that $f:[1,\infty)^2\to[1,\infty)$ is associative if $$f(f(a,b),c)=f(a,f(b,c))$$ And symmetric if $$f(a,b)=f(b,a)$$ e.g. the arithmetic operations '+' and '$\cdot$' are associative and ...
3
votes
3answers
105 views

How do I show that as $z \to \infty$ that $\int_0^\infty \frac{t - \lfloor t \rfloor - 1/2}{z + t} dt = O(z^{-1} )$??

How do I show that as $z \to \infty$ we have $$ \int_0^\infty \frac{t - \lfloor t \rfloor - 1/2}{z + t} \,dt = O(z^{-1} )? $$ According to Serge Lang, the integral on the left is the error term for ...
6
votes
2answers
111 views

Asymptotic form of the integral $\int_{0}^{\infty} dx ~ \sqrt{x^2 + wx} ~ e^{-ixs}$ for $s \to \infty$

I would like to find an asymptotic form of the following integral when $s \to \infty$ ($s$ and $w$ are positive) \begin{equation} \int_{0}^{\infty} dx ~ \sqrt{x^2 + wx} ~ e^{-ixs} \end{equation} I ...
4
votes
2answers
144 views

Closed form for $ \prod_{k=1}^n (a+k^2) $

I have come across the following product: $$ \prod_{k=1}^n (a+k^2) $$ where $a$ is a positive constant. Could anyone suggest a closed form for this product? I need to approximate this for large $n$, ...
3
votes
2answers
699 views

Asymptotic expansion of the complete elliptic integral of the first kind

The complete elliptic integral of the first kind is defined as $$K(k) = \int_0^{\pi/2} \frac{d x}{\sqrt{1 - k^2 \sin^2 x}}.$$ I would like to derive (at least the first term of) the asymptotic ...
2
votes
0answers
107 views

$f(x)\sim 1/x \implies (1+f(x))^x\to e$, but what family of functions maximizes the speed of convergence from below?

This problem is subordinate to finding out if $$\left(1+\frac{\log p_{n+1}}{p_n}\right)^{p_{n+1}/\log p_n},$$where $p_n$ is the $n$-th prime, never stabilizes above or below its limiting value, which ...
1
vote
1answer
55 views

Multiplication of two asymptotic expansions

I have two functions $g, f:(0,\infty)\rightarrow \mathbb{R}$ with asymptotic power series as follows: For all $N\in\mathbb{N}:$ $$f(t) \sim \sum\limits_{n=0}^{N} a_n t^n + O(t^{N+1}) \text{ }\text{ }...
0
votes
1answer
76 views

Prove $\lim_{n \to \infty}$ $(1+\frac xn-o(\frac 1n))^n=e^x$ [duplicate]

We know that $\lim_{n \to \infty}$ $(1+\frac xn)^n=e^x$. How to prove that $\lim_{n \to \infty}$ $(1+\frac xn-o(\frac 1n))^n=e^x$? Attempt of the proof: Let $\epsilon>0$ $\exists n_0$ such that $...
2
votes
0answers
103 views

Method of stationary phase for double integrals

I am looking for a reference for the leading term in the asymptotics of a double integral over a finite rectangle R of $K(x,y)\exp(i \,t\, h(x,y))$ as $t \to \infty$ in the following situation: the ...
1
vote
1answer
58 views

Weyl's law, meaning of the asymptotic formula, does it imply a bound?

Weyl's law states the eigenvalues of the Laplacian behave as $$\lambda_j \sim f(n)j^{\frac 2n}\quad\text{as $j \to \infty$}$$ where $n$ is the dimension. Does this literally mean that, $$\lim_{j \to \...
2
votes
2answers
72 views

How to bound the tail of p-series

How can I asses $S_n = \sum_{j=n}^\infty\frac{1}{j^p}, p>1$ in terms of $n$, specifically can I get something like $$S_n = O(?)$$
1
vote
2answers
30 views

How to prove $\omega$ bound without using limit?

How to show $n^{3.4} - 2015n^{2} + 3$ $\in$ $\omega(n^{3})$ without using limit? According to the definition of $\omega$, $f(n)$ $\in$ $\omega(g(n))$ if and only if $\forall c > 0$, $\exists n_0$ ...
1
vote
1answer
121 views

Density of primes in a polynomial

Consider that $p(x)$ is an irreducible polynomial with integer coeficients, that $\mathrm{gcd}$ of its coefficients is $1$. What is the natural density of the below set? $$A = \{n\ |\ p(n)\ \text{is ...
-1
votes
3answers
65 views

The curve $x^3-y^3=1$ is asymptotic t the line $x=y$. Find the point n the curve farthest from the line $x=y$. [duplicate]

The curve $x^3-y^3=1$ is asymptotic t the line $x=y$. Find the point in the curve farthest from the line $x=y$ This is just need of further details in this ...
0
votes
1answer
40 views

How do I find the equivalence of the expression $e^{n\log(n)-(n+e)\log(n + e)}$?

We want to find equivalence of the expression $$e^{n\log(n)-(n+e)\log(n + e)}$$ Note that: $$\log(n+t)=\log\left[n\left(\frac{t}{n}+1\right)\right]=\log(n) + \frac{t}{n} +o\left(\frac{t}{n}\...
2
votes
3answers
110 views

$u_n=\exp( n\log n-(n+\epsilon)\log(n+\epsilon))$

how can i show this sequence $u_n$ is divergent: $$u_n=\exp( n\log n-(n+\epsilon)\log(n+\epsilon))\quad n\in \mathbb{N}^*;\quad \epsilon \in (0,1)$$ My attempts: \begin{align*} u_n&=\exp( n\log ...
1
vote
0answers
26 views

Is $f(n)=O(g(n))$ or $f(n)=\Omega(g(n))$ when $f(n) = (\log n)^{\log n}$ and $g(n) = n/\log n$?

I have showed that $f(n)=\Omega(g(n))$ in the following way. We assume that $${\log n}^{\log n} \leq n/\log n$$ $$\implies \log n \times \log \log n \leq \log n - \log \log ...
1
vote
0answers
44 views

If I colour $n$ vertices independently, randomly with $n^{(1-x)}$ colours, why is the size of the colour classes $(1+o(1))n^x$?

By $o(1)$, I mean 'little-o' of $1$. A paper I'm reading uses this result, but I can't see where it comes from. Thanks.
1
vote
1answer
59 views

Can we deduce that $⌊r^{n}α⌋≃r^{n}α$ when $r→∞$?

Let $α∈(0,1)$ be an irrational number and let $n≥1$ be a fixed positive integer. For any $r>4$ we define the positive integer $$k=⌊r^{n}α⌋$$ where $⌊.⌋$ denotes the floor function. My question is: ...
1
vote
2answers
183 views

Finding big O of a function

How do I find Big O of function which are polynomial fractions $$f(x) = \frac {x^4 + x^2 + 1}{x^3 + 1}$$ The same question is posted here (Finding Big-O with Fractions) but i dont understand the ...
0
votes
0answers
97 views

Find a big-O estimate for $f(n)=2f(\sqrt{n})+1$

Is the answer from the below linked question correct for my question? Or does the differing of $+ \log(n)$ instead of $+1$ change the outcome of the master theorem? Similar question here
1
vote
1answer
156 views

Asymptotic behaviour of a recurrence relation - How to solve

I'm going over a chapter in recurrence relations in preparation for job interviews and came across the following. I'd like to gain some better understanding of how to solve such a question. Find a ...
2
votes
0answers
32 views

Asymptotic behaviour of $\sum_{k=0}^\infty \frac{n^k}{(k!)^\nu}$

Let $\nu>0$ be fixed. I am interested in the asymptotic behaviour of the series \begin{equation*}s(n,\nu)=\sum_{k=0}^\infty \frac{n^k}{(k!)^\nu} \end{equation*} in the limit $n\rightarrow\infty$. ...
0
votes
1answer
92 views

How do i prove this inequality

Im trying to prove that $f(n)=an^2 +bn+c$ where $a,b,c$ are constants is $\Theta(n^2)$ through inequalities. $$0 \le c_1n^2 \le an^2 + bn + c \le c_2n^2 \text{ for all } n \ge n_0$$ The book gave an ...
3
votes
1answer
82 views

Find this limits $\lim_{n\to\infty}n^2\bigl(n(H_{2n}-H_{n}-\ln{2})+\frac{1}{4}\bigr)$

Question1: Find this limits $$\lim_{n\to\infty}n^2\left(n(H_{2n}-H_{n}-\ln{2})+\dfrac{1}{4}\right)$$ where $$H_{n}=1+\dfrac{1}{2}+\dfrac{1}{3}+\cdots+\dfrac{1}{n}$$ Question 2: ...
0
votes
1answer
33 views

How to derive bounds for the $n$-th term of a subsequence of $\mathbb {N} $, knowing two functions “squeezing” the number of the terms below $x$?

Let $ a_n $ be the $n $-th term of an infinite strictly increasing subsequence of $ \mathbb{N}$ and denote with $\nu(x)$ the number of terms smaller than or equal to $x$. Assume also $$f(x)<\nu(x)&...
2
votes
2answers
154 views

Asymptotic expansion of double integral

Define $$G(\theta) = \int\limits_0^\infty \int\limits_0^{2\pi} \frac{r\,e^{-r^2/2t}}{\sqrt{1-(\sin\theta\sin r \cos\varphi + \cos \theta \cos r)^2}} \mathrm{d} r \,\mathrm{d} \varphi$$ Clearly, for $\...
1
vote
0answers
56 views

Two closest sums of pairs of reciprocals

Trying to obtain a better bound for a problem from this bounty question, I obtained the following problem. Let $n\ge 3$ be a natural number. The problem is to estimate (in particular, asymptotically) ...
1
vote
1answer
22 views

for [ f(n) = Sum(1:n) , g(n) = n^2 ] , why does ( f isIn O(g) AND g isIn O(f) ) hold?

An exercise solution claims that for f(n) = Sum(1:n) , g(n) = n^2 it holds that f isIn O(g) and g isIn O(f). I don't understand why this is, as it seems to me that f isIn O(n) and g isIn O(1), ...
1
vote
3answers
414 views

Big O notation and polynomials

I often see that the following polynomial can be written as such: $f(x) = 6x^4+3x^3+O(x^2)$ where the big O collects all the lower order terms. Yet, I also see this sometimes: $f(x) = 6x^4+7x^9+O(...
1
vote
1answer
35 views

Asymptotic Growth: little o(n) versus $O(n^\alpha)$

Let $f(n) \geq 0$ be defined for all $n \in \mathbb{N}$. Suppose $f(n)$ is $o(n)$ and at the same time $f(n)$ is not $O(n^\alpha)$ for all $0 \leq \alpha < 1$. Is this necessarily a contradiction? ...
3
votes
1answer
68 views

Sum of squares of Binom(n,p) values

Let $x_{n,p}(j)$ be the probability that a random variable distributed according to a binomial distribution with parameters $n \in \mathbf{N}_+$ and $p \in (0,1)$ takes the value $j \in \{0,1,\ldots,n\...
0
votes
0answers
104 views

Asymptotic behavior of divergent $p$-series

I am intertested in the asymptotic scaling behavior of the divergent $p$-series $$ \sum_{k=1}^n \frac{1}{k^p} $$ for $0<p<1$, i.e., is there a closed-form sequence $a_n$ so that $$ \lim_{n \to \...
1
vote
0answers
23 views

Fitting curves by extrapolating known behaviours in certain limits?

I have been studying how a the rotation and translation of a sliding disc (think of it as a hockey puck) is affected by uniform friction. I encountered an integral that I was not able to solve, and ...
0
votes
0answers
90 views

Big Oh Complexity of the algorithm “for $i=1$ to $z$, for $j = 1-X(i)$ to $Y(i)-n^2$ set $k=0$”

I've got a past paper algorithm question I'm trying to complete. I was hoping you could helped me, if so great if not then it's fine :P if you can keep in mind ironically (yep cs student) I'm not ...
0
votes
1answer
59 views

find an asymptotic expansion by using the Watson's theorem

I want to apply the Watson's theorem to find an asymptotic expansion for the function $$f(z)=\int_{- \infty}^{\infty} e^{-z \frac{y^{2}}{2}} \sin(y^{2})dy$$ (Assume $z \rightarrow \infty, z>0$). ...
1
vote
1answer
30 views

Getting tight asymptotic upper and lower bounds of product logs

Consider $$ E(n)=\log_2\left(\log_2 (4)\right) +\log_2\left(\log_2 (5)\right) ... \log_2\left(\log_2 (n)\right) $$ This is equal to $$E(n)= \log_2\left(\log_2 (4)*\log_2(5)*\log_2(6) ... \log_2(n)...
0
votes
1answer
35 views

Graphic intersecting asymptotes

Sometimes graphics intersect the asymptotes(horizontal) of the function we plot and then they tend to the asymptote to infinity.What gives us the information whether the graph only tends to the ...
0
votes
1answer
52 views

asymptotic expansion for Bessel function $I_0(z)$ in terms of Gauss hypergeometric functions ${}_2F_1$

On the Wikipedia page one can asympotoic formula of the Bessel function $$ I_0(z) \propto \frac{e^z}{\sqrt{2\pi z}} $$ On the Wolfram page there is a more detailed asymptotic formula for the Bessel ...
7
votes
2answers
195 views

Asymptotics of $\int_{0}^{+\infty}\!\!\frac{dx}{\sinh^2(\epsilon \sqrt{x^2+1}) } $ for $\epsilon$ near $0$

How to find an asymptotic expansion, for $\epsilon$ near $0$, of the following integral $$ I(\epsilon):=\int_{0}^{+\infty}\frac 1{\sinh^2 (\epsilon \sqrt{x^2+1}) } {\rm d}x. $$ As $\epsilon \...
5
votes
1answer
46 views

Can $f(x+1) = f(x)^{\ln(x)}$ be expressed as integral transform $\int g(x,t) dt $?

Let $x$ be a real number. Can some real-analytic function $f$ that satisfies for $x>3$ :$f(x+1) = f(x)^{\ln(x)}$ be expressed by standard functions as an integral transform : $$f(x) = \int_0^{\...
5
votes
2answers
88 views

How find this sum $\sum_{k=0}^{n}\binom{n}{k}|n-2k|$ closed form or asymptotic behaviour?

Find the following series closed form or asymptotic behaviour $$\dfrac{\displaystyle \sum_{k=0}^{n}\binom{n}{k}|n-2k|}{2^n}$$ I use wolfram can't give the closed form: see wolfram ,so I think ...
0
votes
1answer
72 views

Time complexity and Stirlings approximation

We have an operation that is $O(\sum_{i=1}^{n^2}\log(i))$. Is this valid?: $= O(\log (n^2!)) = \{\text{Stirling}\} = O(\log((n^2)^{n^2})) = O(n^2 \log(n^2)) = O(n^2 \log(n))$ If so, what's an '...
1
vote
2answers
94 views

How to prove the gaussian functions are linear independent?

Assume that I have N Gaussian functions with different means $\mu_i$ and variances $\beta_i$, How to prove $e^{-\beta_i(x-u_i)^2}$ are linear independent? 1$\le$i$\le$N
1
vote
4answers
67 views

Why do we have $u_n=\frac{1}{\sqrt{n^2-1}}-\frac{1}{\sqrt{n^2+1}}=O(\frac{1}{n^3})$?

Why do we have $u_n=\dfrac{1}{\sqrt{n^2-1}}-\dfrac{1}{\sqrt{n^2+1}}=O\left(\dfrac{1}{n^3}\right)$ $u_n=e-\left(1+\frac{1}{n}\right)^n\sim \dfrac{e}{2n}$ any help would be appreciated
13
votes
2answers
327 views

$f=\underset{+\infty}{\mathcal{O}}\bigr(f''\bigl)$ implies that $f=\underset{+\infty}{\mathcal{O}}\bigr(f'\bigl)$.

Let $f\in\mathcal{C}^2(\Bbb{R},\Bbb{R})$ be a positive function such that $f=\underset{+\infty}{\mathcal{O}}\bigr(f''\bigl)$ does it implies that $f=\underset{+\infty}{\mathcal{O}}\bigr(f'\bigl)$? ...
6
votes
1answer
86 views

How does the size of the set $A(R) = \{(a,b) \; | \; a,b \in N \times N, \; \gcd(a,b) = 1, \; a^2 + b^2 \leq R^2\}$ grow?

How does the size of the set $$A(R) = \{(a,b) \; | \; a,b \in \mathbb{N} \times \mathbb{N}, \; \gcd(a,b) = 1, \; a^2 + b^2 \leq R^2\}$$ grow as a function of $R$? My try: It's clear that $|A(R)| \...