Questions tagged [asymptotics]
Questions involving asymptotic analysis, including growth of functions, Big-O notation, Big-Omega and Big-Theta notations.
-5
votes
0answers
20 views
Asymptote of the given curve
What is Asymptote of
$y=x+\frac{1}{x}$
Please explain...in my book a expansion is written but i get asymptotes easily just equation the coefficients of x and y to zero.
0
votes
0answers
16 views
Integration problem (contour?)
I'm trying to solve $$A_2\int_{0}^{1}\frac{A\sqrt{t(1-t^2)}}{2(t^2-1)}e^{zt}dt = \frac{e^{z}}{\sqrt{z}},$$
where $A_2$ is a constant. Would Watson's lemma apply here?
0
votes
0answers
19 views
Simple contour integration problem
I have the differential equation
$2zw'''+5w''-2zw'-3w=0$
to which I pick an ansatz of the form $w(z) =\int_{C}^{} P(t)e^{zt} dt.$
Solving, I find $P(t) = \frac{A\sqrt{t(1-t^2)}}{2(t^2-1)}.$
For $...
1
vote
1answer
14 views
What is the rate of growth of $M_n := \max_{1 \le i \le n} U_i^{(n)}$, where $U_i^{(n)} \sim \operatorname{Uniform}[0,n]$?
On pp. 370-374 (see this previous question) of Cramer's 1946 Mathematical Methods of Statistics, the author shows that for any continuous distribution $P$, if $X_1, \dots, X_n \sim P$ are i.i.d., then ...
0
votes
1answer
37 views
Is $T(n,m) = 2\, T(n-1, (m-1)(1-1/n))$ polynomial in $n$ and $m$? [on hold]
Can you prove or disprove that $T(n,m)=2T(n-1, (m-1)(1-\frac{1}{n}))$ grows polynomially in $n$ and $m$?
If it matters, $T(1, j) = 1$ and $T(i, 1) = 1$.
Usually $m$ is much greater than $n$, or at ...
1
vote
0answers
17 views
Asymptotic distribution of Gini's mean difference
"Derive the asymptotic distribution of Gini's mean difference, which is defined as $$\binom{n}{2}^{-1}\sum\sum_{i<j}|X_i - X_j|."$$
This is a problem from chapter 12 in Van Der Vaart - Asymptotic ...
0
votes
0answers
29 views
A bridge between the sum of the divisors and the Totient function
Let's consider: $$\tau(x,a,b)=\sum_{1 \le d \le x \\ (d,x)=d^a \\} d^b$$
Where $(q,r)$ denotes the gcd of $q$ and $r$.
I think this could be interesting thing to look at because it's somehow a ...
0
votes
0answers
11 views
Asymptotic Behavior to solve differential equation
I was trying to understand how to solve Schrödinger equation for hydrogen atom (in spherical coordinates). Every thing was fine till I came across an equation which I could not understand: equation (4....
2
votes
1answer
21 views
Conditional expectation $E(X_1 \mid \overline{X}_n)$ if $X_1,\dots,X_n$ are i.i.d. Am I correct?
Contitional expectation $E(X_1 \mid \overline{X}_n)$ if $X_1,\dots,X_n$ are i.i.d.
Since $X_1,\dots,X_n$ are i.i.d, then $E(X_1 \mid \overline{X}_n) = E(X_1)=\overline{X}_n)$
Am I correct in ...
0
votes
2answers
46 views
Why Is This Algorithm Not In Polynomial Time?
so recently my professor went over this algorithm and stated that this is not a polynomial time algorithm due to n not being the length of the input. Can somebody explain why this is so? I didn't ...
2
votes
0answers
44 views
Probability of being in same connected component
I would like to answer the following basic question:
Let $V$ be a collection of $n$ vertices and fix $x$ and $y$ in $V$. Let $G$ be a random graph on $n$ vertices and $M$ edges. What is the ...
3
votes
1answer
62 views
For sufficiently large $n$, Which number is bigger, $2^n$ or $n^{1000}$? [duplicate]
How do I determine which number is bigger as $n$ gets sufficiently large, $2^n$ or $n^ {1000}$?
It seems to me it is a limit problem so I tried to tackle it that way.
$$\lim_{n\to \infty} \frac{2^n}{...
0
votes
0answers
13 views
Question about comparing $n^c$ & $log n$ in term of big o
I am doing exercise on Big o and I mean this True false question:$(n^{1.99} )*(log^5 n) = O(n^2) $
by turning $n^2=n^{1.99} \times n^{0.01}$, the question becomes comparing $n^{0.01}$ with $\log^5 n$,...
4
votes
3answers
88 views
Is there a parabola which is similar to a branch of hyperbola?
Parabola and a branch of hyperbola, visually looks similar.
The only difference I find is that, when x tends to infinity, hyperbola approaches a straight line (asymptote). Whereas if I draw an ...
2
votes
1answer
36 views
Volume of the unit sphere converges to $0$ faster than any $a_n := a^n$ with $0<a<1$.
I do not know how to solve the following problem:
Prove that the volume of the $n$-dimensional unit-sphere converges faster to >$0$ than any sequence of the form $a_n := a^n$ for $0<a<1$.
I ...
2
votes
1answer
41 views
Big O of multiple variables
Let $g(x, y, z)$ be a polynomial in the three variables $x, y, z$ that take values in $\mathbb{N}$. Prove
that $g(x, y, z) = \mathcal{O}(x^k y^l z^m)$
for some $k, l, m \in \mathbb{N}$
I am not ...
3
votes
3answers
71 views
What is the asymptotic order of $\sum_{k=0}^n {n\choose k}^2$?
What is the asymptotic order of $\sum_{k=0}^n {n\choose k}^2$? That is, find $g(n)$ such that $$\lim_{n\to \infty}\frac{\sum_{k=0}^n {n\choose k}^2}{g(n)}=1$$
We can expand the binomial coefficient ...
-1
votes
1answer
13 views
what is the order of growth of the following sum? [closed]
what is the order of growth of the following sum ?
$$
\sum_{i=1}^n \left(i^2+1\right)^2
$$
1
vote
1answer
39 views
Bounding the extrema of polynomials from $\frac{d^n}{dx^n} \exp(-1/x)$
As laid out on Wikipedia, the function
$$f(x):=\begin{cases} \exp(-1/x) & x>0\\ 0 & x\le 0 \end{cases}$$
has the expression for derivatives at $x>0$,
$$ f^{(n)}(x) = \frac{p_n(x)}{x^{...
4
votes
2answers
62 views
Asymptotic of sum $\sum_{j=1}^n j^{f(n)}$
What is known about the asymptotic of $\sum_{j=1}^n j^{f(n)}$ where the exponent is some function that grows with $n$? For instance, if $f(n) = k$ is constant, then we know it's $\frac{1}{k+1}n^{k+1} ...
0
votes
0answers
21 views
How correct an estimate for twin primes obtained from the Rosser-Iwaniec sieve and Prime number theorem for arithmetic progressions could be?
Let $P$ be the set of primes $p$, $x \geq D \geq z^2 \geq 2$, and let $A⊂[1,x]$ be a set of integers. Suppose $A_{d}=|A| \frac{v(d)}{d}+R_{d}$ for square free d with $v$ being multiplicative and $v(p)$...
2
votes
0answers
27 views
Might there be a Skewes number for semiprimes?
Briefly the question here is whether there is or could be a theorem analogous to that of Littlewood for semiprimes (generalized prime numbers which are products of two primes, repetitions allowed), ...
1
vote
1answer
56 views
Obtain the leading order uniform approximation of the solution
Obtain the leading order uniform approximation of the solution to $ \epsilon y′′-x^2y′-y=0$.
The boundary conditions are $y(0)=y(1)=1$.
Since $a(x)<0$ the boundary layer is at $x=1$.
The outer ...
0
votes
1answer
11 views
comparing Asymptotic functions $ 3^{{2}^{n}}$ and $n! \times n^{3}$
$f(n)= 3^{{2}^{n}}$
$g(n)=n! \times n^{3}$
$\text{which is asymptotically greater} ?$
My Approach-:
$$f(n)=e^{\log 4^{{3}^{n}} }$$
$$g(n)=e^{\log n! \times n^{3}}$$
i am comparing just the ...
3
votes
1answer
72 views
How accurately must I compute the twin prime constant to get the twin prime density?
Let $\pi _{2}(x)$ denote the number of primes $p\leq x$ such that $p+2$ is also prime. Hardy and Littlewood conjectured that
$$
{\displaystyle \pi _{2}(x)\sim 2C_{2}{\frac {x}{(\ln x)^{2}}}\sim 2C_{2}...
-1
votes
0answers
42 views
$T(n)=nT(n−1) + 1$
I'm trying to figure out the order class of this recursion, I know it is of the order $O(n!)$ using substituting method.
$T(n)=n⋅T(n−1)+1$
$T(1)=1$
But I am wondering why I cant apply masters ...
2
votes
1answer
31 views
Asymptotic expansion of heat operator $e^{-\Delta{t}}$ and $e^{-\mathcal{D}t}$ of Dirac operator
For a closed Riemannian manifold $M$ of $n$-dimension, we consider the Laplace-Beltrami operator $\Delta$.
It is known that we have an asymptotic expansion for the trace of heat operator $e^{-\Delta{...
0
votes
0answers
17 views
Generalizing $n \cdot m = O(n^2) \iff m = O(n)$ to any two-variable function
I came across the following statement in my Computer Science high-school textbook (I translated it to English).
There was some for loop that runs $m$ times nested inside a for loop that runs $n$ ...
-1
votes
0answers
23 views
Why is it true that $\sqrt{\frac{a}{2x}+O(x^{-2})} = \frac{a}{4x} + O(x^{-2})$ for $|x|<1$
Simplify $\sqrt{\frac{a}{2x}+O(x^{-2})}$ for $|x|<1$. This problem uses "big-O" notation where $f(x) = O(g(x))$ as $x\rightarrow a$ if and only if there exists positive numbers $M$ and $\delta$ ...
2
votes
2answers
43 views
Solve for $k$ if $\beta^kk!\ge (1-\alpha)/\alpha$.
Let $\beta$ be a constant and $\alpha\in (0,1]$. I want to show that for any $\alpha\in (0,1]$ (no matter how small) there exists $k\in\mathbb N$ such that $$\beta^kk!\ge (1-\alpha)/\alpha$$
I used ...
0
votes
0answers
10 views
Survival Analysis Asymptotics
I'm trying to work through the derivation for the asymptotic distribution of the baseline hazard function estimator for the Cox model, but I can't seem to find any literature that works through this. ...
0
votes
0answers
31 views
Calculating upper and lower bound
Suppose there is a function
$\ f(x)= 19n^2/5n +1-n $
I want to calculate upper and lower bound. But I had this confusion that whether I have to calculate in terms of n^2? Because dominating term is n^...
0
votes
1answer
20 views
Showing that an estimator is consistent
Let $X_1,X_2,\ldots,X_n$ be a random sample from $\mathcal{N}(\theta,1)$. Consider the following (randomized) estimator of $\theta$ given a sample of size $n$:
$$
\hat{\theta}_n = \bar{X} + \begin{...
0
votes
3answers
32 views
Find whether $f(x)$ is $O(g(x))$ [whether $f(x)$ is Big-O of $g(x)$]
Given: $f(x)=3^{\sqrt{x}}, g(x) = 2^x$, find whether $f(x)$ is Big-O of $g(x)$, and vice-versa.
I want to use the following fact: $$\lim_{x\to\infty}(\ln|f(x)|-\ln|g(x)|) \leq ln(C) \implies f(x)=O[g(...
1
vote
3answers
49 views
Can I make a line with both a slant asymptote and a horizontal.
Why can’t you create an equation of a line that gets closer to a line as it heads to $\infty,$ such as $y=x$ or $y=2x+4$ and a horizontal asymptote that approaches something like $-2$ as it goes ...
0
votes
1answer
47 views
Can't seem to find the lower bound for this function
Been reading about algorithms. I am trying to find the lower and upper bounds for the function f(n). not very familiar with mathjax so i used mathtype. how do i proceed with the lower bound. ...
4
votes
1answer
48 views
Can we refine this asymptotic for Laguerre polynomials?
I just found an interesting and useful limit for Laguerre polynomials:
$$\lim_{n \to \infty} L_n \left( \frac{2r}{n+1/2} \right)=J_0(2 \sqrt{2r})$$
I'm using specifically this form of the argument ...
3
votes
1answer
69 views
Asymptotic behaviour of recurrence
In DNA chain, there are four types of bases: A, C, G, T. Let $g(n)$ be the number of configurations of a DNA chain of length $n$, in which the sequences TT and TG never appear. Write a recurrence for $...
13
votes
3answers
252 views
Sum of $\{n\sqrt{2}\}$
I would like to prove (rigorously, not intuitively) that
$$\sum_{n=1}^N \{n\sqrt{2}\}=\frac{N}{2}+\mathcal{O}(\sqrt{N})$$
where $\{\}$ is the "fractional part" function. I understand intuitively why ...
1
vote
3answers
61 views
Big O summation and additivity
I'm not sure whether the following equality is correct, or rather, whether my interpretation of it is correct:
$$\sum_{i=0}^n O(f(i)) = O(\sum_{i=0}^n f(i)) \qquad (1)$$
The way I interpret the LHS ...
-1
votes
0answers
21 views
how to find the asymptotic growth of f
The question is:
Let $$S_n=\left\{t\in\mathbb{N}\mid t\text{ does not contain }n\text{ consectuive }4'\text{s}\right\}$$ E.g. $2464\in S_2$, but $2544$ is not.
Let $$f(n)=\sum_{s\in S_n}\frac{1}{s}$$...
3
votes
1answer
113 views
Asymptotic behavior $\sum_{n=1}^x\phi_k(n)$, a variant of Euler's Totient function
Let $$\phi_k(x)=\sum_{1\le n \le x \\(n,x)=1} n^k$$
What's the asymptotic behavior of
$$\sum_{n=1}^x\phi_k(n)?$$
According to the wikipedia $\sum^x_{n=1} \phi_0 (n) \approx \frac{3}{\pi^2}x^2 $. It ...
0
votes
1answer
38 views
Inverse of the asymptotic expansion of Gauss Hypergeometric function
I am interested in obtaining the asymptotic expansion of $r(\rho)$ (which is the inverse of $\rho$ below). Basically I want to series expand $\rho$ for large $r$ (i.e. as $r\to \infty$) and then ...
0
votes
0answers
18 views
Big O inside big O
Is there a definition of big O inside big O, ina way to give a sense to this $O(h(O(g)))$ with $h,g$ functions.
Could be it $O(h(O(g)))=\{ f | \forall k \in O(g) \rightarrow f \in O(h \circ k) \}$ ?
...
0
votes
1answer
25 views
$\frac{c^t e^t}{t^{t+1/2}}$ and $e^{-kt^2}$ which decay faster as $t \rightarrow \infty$？ where $c$ is constant
$\frac{c^t e^t}{t^{t+1/2}}$ and $e^{-kt^2}$ which decay faster as $t \rightarrow \infty$？ where $c,k$ are constants . how to see that?
2
votes
1answer
29 views
Compare two algorithms with each other
I am fairly new algorithms and the math behind it.
I am very sorry if this is the wrong place to ask if so please let me know and I can delete this question.
I would need help with the following ...
0
votes
1answer
35 views
how to prove that $f(n)=n^3+n\log^2n$ = $\theta(n^3)$?
i have $f(n)=n^3+n\log^2n$
and i was trieng to prove that $f(n)=n^3+n\log^2n$ = $\theta(n^3)$. but i feel that i am doing it all wrong , which means i understand why the statent is true but i don't ...
0
votes
1answer
54 views
How to prove that $r_n=r_{n-1} - \frac12 b r_{n-1}^2 $ is asymptotic to $\frac{1}{n}$?
So my question is:
How do we prove that $r_n=r_{n-1} -\frac12 b r_{n-1}^2 $ is asymptotic to $\frac{1}{n}$ when we have an offspring distribution $p_i:=P(\xi=i)$ and b is the variance
$$b=\sum_{i\geq ...
-2
votes
0answers
20 views
Are Primorials The Worst Case On Euler's Phi Function?
For each positive integer k, let Pk denote the product of the first k primes. We have φ(Pk)=θ(Pk/loglogPk).
This shows that φ(n) could be as small as (about) n/ log log n for infinitely many n.
Show ...
0
votes
0answers
12 views
Order in probability of a ratio between two integrals
Suppose that $\mu$ is an adapted bounded stochastic process and suppose that $\sigma$ is an adapted bounded left-continuous stochastic process. I want to prove that
$$
\frac{\int_0^{\Delta}\mu_s\,...
