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
0answers
50 views

Big-O estimate (smallest order)

I'm trying to give a big-O estimate for each of these functions, where I want to use a simple function $g$ of smallest order. I have them all done I just wanted to someone to run through and check ...
1
vote
0answers
42 views

Asymptotics of expectation of a ratio of binomially distributed random variables

Let $X_n \sim Bin(n_1,p_1)$ and $Y_n \sim Bin(n_2, p_2)$ with $n_1 + n_2 = n$ and $p_1,p_2 >0$ be independent, binomially distributed random variables. We furthermore assume that $\frac{n_1}{n} \to ...
1
vote
0answers
27 views

Asymptotic behaviour of $\varphi''(x)=F(\varphi(x))$

I'm concerned with the discussion of a ODE, especially the discussion of the solution. I've got the assumptions that there is the relation $\varphi''(x)=F(\varphi(x))$ for all $x$ on $\mathbb{R}$. ...
1
vote
0answers
41 views

sum over primes involving divisor function (variation of the Titchmarsh divisor problem)

Does there exist an asymptotic estimate for the following sum over primes $$ \sum_{p\leq x} \frac{\tau(p-1)}{p}\;, $$ where $\tau(n)=\sum_{d|n}1$ is the divisor function?
1
vote
0answers
34 views

Using Limits to Determine Big-O, Big-Omega, and Big-Theta

I am trying to get a concrete answer on using limits to determine if two functions, $f(n)$ and $g(n)$, are Big-$O$, Big-$\Omega$, or Big-$\Theta$. I have looked at my book, my lecture notes, and have ...
1
vote
0answers
14 views

Recursive relation-Theta notation

Consider the recursive relation: $$T(n)=T(an)+T((1-a)n)+cn$$ where $0<a<1$ and $c>0$ are constants(independent of $n$).Show that $T(n)=\Theta(n \lg n)$ That's what I have tried: We ...
1
vote
0answers
59 views

Find a closed form for the constant term

In a previous question, an asymptotic expansion was provided for the weighted divisor summatory function $\displaystyle \frac {d(n)}{n}$: $$\sum_{n\leq ...
1
vote
0answers
35 views

Asymptotic behaviour / Convergence

Let $0<\omega<\infty, \mu >0$ and $z \in \mathbb{R}.$ In my book, it is written that we have the following asymptotic behaviour: i) Claim: $$\lim_{t \rightarrow \infty} \frac{z ...
1
vote
0answers
26 views

How to show an aymptotic expansion is uniformly valid?

I have an equation $$ nt = u - \epsilon \sin(u) $$ which asks for the first four terms in the asymptotic solution. Hence if the solution is $u_0 + \epsilon u_1 + \cdots.$, expand $\sin(u)$ around ...
1
vote
0answers
54 views

Definition of $O (.) $ notation

The book I am currently reading defined the big oh operator as the following: A function $ g (x) $ said to be $ O (h (x)) $ as $ x \to l $ if $\lim \sup_{x \to l} |g (x)/h (x)| < \infty $. What I ...
1
vote
0answers
38 views

What is the sign of the generalized Stieltjes constants $\gamma_{k}(a)$?

Recall that the Stieltjes constants $\gamma_{k}$ appear as the coefficients in the regular part of the Laurent expansion of the Riemann zeta function about $s = 1$: $$ \begin{align} \zeta(s) = ...
1
vote
0answers
28 views

Asymptotic behavior of sums of consecutive powers (bivariate)

Are there some (bivariate) closed form formulas for the asymptotic behaviour of the sum: $$\sum_{k=1}^{n} k^d,$$ where $n$ and $d$ are large integers? I am especially interested in a lower bound of ...
1
vote
0answers
40 views

Approximations for finite n in limit-based definition of the exponential function

The exponential function can be defined via: $$ e^x = \lim_{n \rightarrow \infty} \left( 1 + \frac{x}{n} \right)^{n} = \lim_{n \rightarrow \infty} g(x; n) $$ In my problem, I actually have the right ...
1
vote
0answers
32 views

Question about finite sums and integer recursions.

Let $n$ be a positive integer and let $g(n)$ be a given strictly increasing integer function such that $0<g(n)<n$ for all $n$. Also the sequence $ |g(n) - n|$ is unbounded as $n$ grows. Let ...
1
vote
0answers
63 views

Long-time asymptotic behaviour of a system of two ODEs

We have the following nonlinear ODE: $$ f' = af-bg -(f+g)^k \bigl(f'(0) +g'(0)\bigr) + f'(0), $$ $$ \bigl(G-T(x)\bigr) g' = -af+bg - g'(0), $$ where $a,b,k,G$ are constants, $f'(0)$ and $g'(0)$ are ...
1
vote
0answers
28 views

What is the power series for a half-exponential function?

What is the power series of a half-exponential function? Half-exponential means that $f(f(x)) = y^x, y > 1$
1
vote
0answers
31 views

How can I show that the solution of the recursive realtion is $O(n \lg n)$?

Show that the solution of the recursive relation $T(n)=2T( \lfloor \frac{n}{2} \rfloor +17)+n$ is $O(n \lg{n})$. I am supposed to use the substitution method.. That's what I have tried: Let ...
1
vote
0answers
17 views

asymptotic approximation for number of partitions of integer that do contain 1 nor 2

Hardy and Ramanujan provided a famous asymptotic approximation to $P(n)$ the number of partitions of an integer $n$ when $n$ gets large. I wonder if there is an asymptotic approximation to ...
1
vote
0answers
24 views

Asymptotic behavior of oscillatory Hilbert transform

Does anyone know what is the leading term in the asymptotics of $$ P.V. \int\limits_{ -\infty }^{ +\infty } \frac{e^{i \lambda x^3 } f( x ) dx }{ x }, $$ as $ \lambda \to +\infty $? Assume $ f \in ...
1
vote
0answers
48 views

Sums of Power Law random variables

Suppose $F$ be a pareto distribution with scale parameter $x_m$ and shape parameter $\alpha$. Assume $X_1, X_2 , ..., X_n$ are iid random variables drawn from $F$. Let $S_n(k) = X_1 ^k + X_2 ^k + ...
1
vote
0answers
32 views

Help understanding this approximation

In a paper that I'm reading, the authors write:- $$N_e \approx \frac{3}{4} (e^{-y}+y)-1.04. \tag{4.31}$$ Now, an analytic approximation can be obtained by using the expansion with respect ...
1
vote
0answers
24 views

asymptotics of the solution of an integral equation

Suppose we are given the integral equation $$ u(x;a) =v(x)+\int_0^a K(x,y)\,u(y;a)\,dy, $$ where $K(x,y)$ and $v(x)$ are known functions, and $a>0$ is a constant. What I am interested in is the ...
1
vote
0answers
86 views

Does the index of a curve determine the asymptotic behaviour of certain vector fields?

There are a collection $C$ of charges in $\mathbb{R}^2$ which cause an electric vector field $V$ to form. Each charge's contribution to $V$ follows the inverse-square law. Let $\gamma$ be a curve ...
1
vote
0answers
50 views

Integration vs Summation

I am interested in how one might generally evaluate, or estimate $$G(x)=\sum_{n=1}^{\infty}f(n)x^n-\int_{0}^{\infty}f(t)x^tdt$$ as $x\to1^-$, and for a continuous $f$, and such that the integral ...
1
vote
0answers
62 views

Prime Zeta Function

Does $$\sum_{p \text{ prime}} \frac{1}{p^s} \sim \log \zeta(s) \quad \text{as} \quad s \to 1^+$$ imply $$\sum_{p \leq n} \frac{1}{p} \sim \log H_n \quad \text{as} \quad n \to \infty,$$ where $H_n$ is ...
1
vote
0answers
124 views

Limit of sequence of integral related i.i.d. observations

Let $X_1,\dots,X_n$ be i.i.d. random variables, each uniformly distributed on $[0,1]$. Let $\hat F_n$ be their modified empirical distribution function, i.e., $$ \hat ...
1
vote
0answers
34 views

Simplify $\frac{n(k^2-1)}{2}$ to $ nk^2$

How does $\frac{n(k^2-1)}{2}$ become $nk^2$? I'm sorry for the stupid question but I'm at wits end and I have no idea how to go about this. Context Thanks
1
vote
0answers
50 views

Evaluating a Limit with Generalized Harmonic Numbers.

Using WolframAlpha, I could informally come up with the following result: $$ \lim_{n \rightarrow \infty} \frac{H_n^{(-\frac{1}{2})}}{n\sqrt{n}} = \frac{2}{3} $$ Allowing me to infer that ...
1
vote
0answers
99 views

Big-O Notation for remainder terms in Taylor expansion

The Big-O notation is commonly used in Taylor expansions of the form $$f(x+\epsilon)=f(x)+\epsilon f'(x)+O(\epsilon^2)$$ to say that the remainder term grows at least quadratic around $\epsilon=0$. ...
1
vote
0answers
53 views

Integral asymptotics

Is there some kind of a variation of the Laplace's method or some other formula for the asymptotics of integrals of a type $$\int_a^bf(x)e^{mp(x)}\cos(mq(x)+x/2)dx, \ m\to\infty.$$ Here $f,p,q$ are ...
1
vote
0answers
50 views

Is $\log^* (n+1)^{n+2} \in O(\log^* n)$?

I would like to know if $\log^* (n+1)^{n+2} \in O(\log^* n)$, where $\log^*$ is the iterated logarithm. I tried doing: $ \log^* (n+1)^{n+2} =\\ \log^{*}(\log(n+1)^{n+2})-1 =\\ \log^{*}((n+2) \cdot ...
1
vote
0answers
23 views

Asymptotic estimate for an expression of

\begin{equation} A = \frac{(\frac12-\frac{1}{n})(\frac12-\frac{2}{n})...(\frac12-\frac{t-1}{n})}{(\frac{1}{2}+\frac{1}{n})(\frac{1}{2}+\frac{2}{n})... (\frac{1}{2}+\frac{t}{n})} \end{equation} Can we ...
1
vote
0answers
88 views

Asymptotic estimate of coprime pairs of integers $\leq n$.

Let $M_{n} = \{(x,y) \in [n] \times [n]: xy \leq n^{2} \text{ and } gcd(x,y) = 1\}$, where $[n] = \{1, 2, \dots , n\}$. In other words, let $M_{n}$ be the set of pairs of coprime integers both $\leq ...
1
vote
0answers
132 views

Method of dominant balance and perturbation theory

We know perturbation theory express the desired solution of differential equations in terms of a formal power series in some "small" perturbation parameters: $y=y_0+\epsilon ^1 y_1+\epsilon ^2 ...
1
vote
0answers
59 views

How to find Laplace approximation for following integral?

Let's have integral $$ I(x) = \frac{1}{2\pi} \int \limits_{-\pi}^{\pi}e^{xcos(\theta )}d \theta, \quad x \to +\infty . $$ How to use Laplace approximation for this integral and find first two ...
1
vote
0answers
41 views

Asymptotics for exponential integrals

Suppose I have a situation where I want to find an asymptotic expansion as $x \to \infty$ for an integral of the form: $$ \int_{a}^{b} f(t) e^{-\phi(t) x} \mathrm{d}t$$ Let us also suppose that ...
1
vote
0answers
36 views

$\lim_{z \to x \pm i \infty} \Gamma(z) \zeta(z + \alpha) = 0$?

I guess $\lim_{z \to x \pm i \infty} \Gamma(z) \zeta(z + \alpha) = 0$ where $x$ and $\alpha$ are real numbers. The guessing is from numerical experiments and I know $\Gamma(z)$ vanishes exponentially ...
1
vote
0answers
38 views

Question about asympotic expansions!! please help!

Question: Find the constants $$a_0, a_1, a_2$$ in the asympotic expansion $$\int_0^x t\sqrt{ln(t)} dt$$ = $a_0(x^2)(lnx)^\frac 12$ + $a_1\frac {x^2}{(lnx)^\frac 12}$ + $a_2\frac {x^2}{(lnx)^\frac ...
1
vote
0answers
32 views

How does one prove that $n^{-100} = \omega(2^{\sqrt{\log{n}}})$?

I feel that $2^{\sqrt{\log{n}}}$ could be dramatically simplified, but I'm sure how. Aside from plugging in huge values to test the functions, any ideas on how I can prove this relationship?
1
vote
0answers
32 views

Frechet differentiability, asymptotic normality

I try to prove the asymptotic normality from the Frechet differentiability. Consider $$T(G)-T(F)=L_{F}(G-F)+o\left(d_{\star}(G,F)\right)$$ and ...
1
vote
0answers
24 views

Prove that if $k^2=o(n)$, then $n(n-1)(n-2)…(n-k+1) \approx n^k$

Prove that if $k^2=o(n)$, then $n(n-1)(n-2)...(n-k+1) \approx n^k$ Do I start by dividing both sides by n^k and collecting terms, perhaps? Not sure. Not entirely sure about the relevance of ...
1
vote
0answers
44 views

Computational Complexity

My question is very basic, it is just so that I have a basic grasp of the terminology of algorithm speed. When someone says an algorithm speed is $O(n^2)$ they say that the number of steps of this ...
1
vote
0answers
55 views

Asymptotic behavior of the Beta function

Let $B(z_1,z_2)$ be the Beta function, $z_1 = x_1 + iy_1$, $z_2 = x_2 + i y_2$. Suppose that $x_1$, $x_2 > 0$. I want to estimate the behavior of $|B(x_1+iy_1,x_2+iy_2)|$ as $|y_1|+|y_2|\to \infty$ ...
1
vote
0answers
52 views

Newton polygon and asymptotic behavior near a singular point

As we know, Newton polygons could be used to determine the Puiseux series of algebraic curves (see, for example, Kirwan's Complex Algebraic Curves, chapter 7). Different branches correspond to ...
1
vote
0answers
35 views

Can I use the Big-O (Landau) notation to “segment” the set of positive increasing real functions?

Let functions $f(n)$ and $g(n)$ be increasing in $n$. I am trying to say the following precisely: As $n\rightarrow\infty$, if $f(n)$ is "smaller" than $g(n)$ then $A$ is true, and if $f(n)$ is ...
1
vote
0answers
24 views

Can an entire $f$ satisfy $x>k | f(x+yi)=\ln(x+yi+z)+o(1) $?

Let $z$ be a complex number. Let $i$ be the imaginary unit. Let $x,y,k$ be positive real numbers. Consider $$x>k | f(x+yi)=\ln(x+yi+z)+o(1) $$ true for all $x>k,y$ and some $k,z$. Is there ...
1
vote
0answers
45 views

Asymptotics for prime factors

Am I correct in assuming that the same result: $$ N_k(x):=\ \mid\{n\leq x : \Omega(n)=k\}\mid \ \sim \frac{x}{\log x}\frac{(\log_2 x)^{k-1}}{(k-1)!}\ (x \rightarrow \infty) $$ also holds for: $$ ...
1
vote
0answers
59 views

Is it possible to find the least common divisor of a two numbers that are not relatively prime in polynomial time?

As the question states: Is it possible to find the least common divisor of two number that are not relatively prime in polynomial time? If so, how? Thanks!
1
vote
0answers
28 views

Find the order of the following expression as x->0

Could someone help me find the order of the following expression without using the quotient rule? $\frac{1-\cos(x)}{1+\cos(x)}$ I expanded the denominator and the numerator but not sure how I get to ...
1
vote
0answers
32 views

Asymptotically evaluating integrals with oscillatory behaviour in both numerator and denominator

I have come across an integral that I would like to asymptotically evaluate (to leading order at least) which I have seen no mention of in standard textbooks. I want to evaluate an integral of the ...