Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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\,...