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
109 views

What is $\int_{\Omega'} \psi (\nabla p) dV \: \text{as} \: \delta\alpha \rightarrow 0$?

I have an axi-symmetric integral (the domain and all functions are axi-symmetric) in cylindrical coordinates which needs to be integrated by parts for use in a finite element code. The integral is ...
0
votes
2answers
67 views

Theorem 3.16. in Analytic Number Theory by Apostol

The below texts are from the book Introduction to Analytic Number Theory by Apostol: I have two questions which I couldn't find solutions for them: $1-$ According to Thm 3.16., $\sum_{n\le x} \...
4
votes
1answer
87 views

Limit of a sum (no probabilities)

Show that $$\lim_{n\to+\infty}\left(\frac{2}{3}\right)^n\sum_{k=0}^{[n/3]}\binom{n}{k}2^{-k}=\frac{1}{2}$$ without using probabilities. $[\;\cdot\;]$ denotes the integer part.
0
votes
0answers
23 views

meromorphic function on torus

Consider the familly of meromorphic function on the square torus (endowed with the corresponding complex structure) with $p$ simple poles and $p$ simple zeros and $L^1$-norm equal to $1$ : $\mathcal ...
0
votes
3answers
38 views

Asymptotics of incomplete Beta function $B_{1/2}(y+1,y)$ when $y\to\infty$

My question concerns the behavior of the incomplete Beta function $$B_{1/2}(y+1,y)=\int_0^{1/2}x^y (1-x)^{y-1}dx$$ in the large $y$ limit. I have been looking everywhere, but I can't find anything. ...
8
votes
1answer
4k views

Formal definition of big-O when multiple variables are involved?

(My apologies if this is a duplicate; I did some searching but didn't turn up anything else like this on the site. Please let me know if it's a duplicate and I'll gladly delete it.) I was reading up ...
0
votes
0answers
22 views

Get an upper bound of $\left| F(1+it) \right|$ in an example of Perron type formula

From Proposition 3 of Tao, A cheap version of Halasz’s inequality, I know how get for example upper bounds for $x,T\geq 1$ $$\frac{1}{x}\sum_{n\leq x}\frac{\mu(n)\log n}{n}\ll\int_{-T}^{T} \left| \...
0
votes
0answers
20 views

Determining bounds for a sum with nested infinite series

I am computing the inner product of the characters of the trivial and the $k$-th irreducible two dimensional representations of the dihedral group $D_n$ of order $2 n$ when $n$ is even. The ...
0
votes
1answer
20 views

An upper bound of $ \left| \frac{1}{s}\log\zeta(s) \right| $ for $\Re s=\sigma>1$, from this integral formula and a related comparison

For $\Re s=\sigma>1$ one has the following known formula $$\frac{1}{s}\log\zeta(s)=\int_1^\infty \Pi(x)x^{-s-1}dx,$$ then if we take the derivative we can write $$\frac{1}{s}\log\zeta(s)=s(s+1)\...
1
vote
2answers
64 views

Testing convergence of series $\sum_{n=1}^\infty\sin(\pi\sqrt{n^2+k^2})$ [duplicate]

Considering $$\sum_{n=1}^\infty\sin(\pi\sqrt{n^2+k^2})$$ depending on $k$, which can be real. I have absolutely no clue how to proceed. Tried to taylor it, but with no result.
7
votes
1answer
672 views

Product of Fibonacci numbers

I'm looking for the asymptotic approximation of the product of the first $n$ Fibonacci numbers. Does there exist a tight approximation for these kind of things?
2
votes
0answers
25 views

How to find the asymptotic expansion of $\int_{-\infty}^{y} e^{-x^2/2}/\sqrt{2\pi} dx$ where $x \in N(0,1)$?

I realize the function inside the integral is the pdf of a normally distributed random variable x, but am unsure how to use this to solve the problem. I am trying to relate it to the inverse of the ...
1
vote
1answer
52 views

When is $1-(1-p)^n \sim pn$

Let $0<p=p(n)<1$ with $p=o(1)$. For which $p$ is it true that $1-(1-p)^n \sim pn$? With $\sim$ I mean that they are asymptotically the same, so $\frac{1-(1-p)^n}{pn}\rightarrow 1$, or at least ...
1
vote
1answer
64 views

How to obtain $N_{\mu, i} (\lambda)=c_n \text{vol} (Q_i) \lambda^{\frac{n}{2}}+o(\lambda^{\frac{n}{2}})$? - Weyl's law

I am trying to prove the Weyl's asymptotic law for eigenvalues. In the document Weyl's law of p. $4$, I have managed to go up to the step $$\tilde{\nu_k} \leq \nu_k \leq \mu_k \leq \tilde{\mu}_k \...
1
vote
1answer
17 views

multiple of an integer and asymptotics

Let us suppose that we have a positive integer $N$. We take the integer $\lceil \log_2 N \rceil$. Does there always exist an integer $X \geq N$ such that the following both conditions are satisfied: ...
2
votes
2answers
348 views

Find the leading order asymptotic behaviour of the integral

$$I(x) = \int_0^{\infty}e^{-t-\frac{x}{t^2}}dt \mbox{ as } x \mbox{ tends to infinity} $$ I know this has a moveable maximum so you need to make a substitution which transforms it into the integral: $$...
27
votes
9answers
7k views

What is the purpose of Stirling's approximation to a factorial?

Stirling approximation to a factorial is $$ n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n. $$ I wonder what benefit can be got from it? From computational perspective (I admit I don't ...
3
votes
0answers
52 views

How quickly can we find a value that has large multiplicative order modulo $n$?

If we're trying to find an element modulo $n$ that has multiplicative order at least $\sqrt{n}$, how quickly can we do this? We don't know if $n$ is prime or composite, only that $n$ definitely has a ...
0
votes
2answers
39 views

$(x + y + xy)/2 = f( f^{[-1]}(x) + f^{[-1]}(y) )$

Consider $(x + y + xy)/2 = f( f^{[-1]}(x) + f^{[-1]}(y) )$ Where $f^{[-1}]$ denotes the functional inverse of $f$. How to find $f$ ? How about the more General idea of finding $f$ for a given $g$? ...
1
vote
0answers
89 views

Find a non-constant real-analytic function $f(x)$ such that for $x\in\Bbb R,\;f(2^x) = f(4^x + 2^{x+1} + 2) - f(4^x + 1)$

Let $f(x)$ be a non-constant real-analytic function and for real $x$ it satisfies : $f(2^x) = f(4^x + 2^{x+1} + 2) - f(4^x + 1)$ Before you ask if this simplifies by writing $2^x = y$ note that $2^...
-1
votes
1answer
39 views

Finding the Time Complexity in Big theta notation [closed]

sum = 0 ; for ( i = 0 ; i < n ; i++ ) for ( j = 1 ; j < n^4 ; j = 4*j ) sum++; How would I go about finding the time complexity in ...
2
votes
1answer
57 views

Does satisfy $f(n)=\frac{\sigma(n)}{n^2}$ the hypothesis of Halasz’s inequality?

Let $\sigma(n)=\sum_{d\mid n}d$ the sum of divisor function. I would like to know if I can write an example of some of the following Theorem 1 or Theorem 2 from $$f(n)=\frac{\sigma(n)}{n^2}$$ in Tao, ...
0
votes
2answers
54 views

Is there an way to calculate the value of O(n) [closed]

Is there an way to calculate the value of O(n) (Big Oh)? I understand it's use in algorithm. But my question is how is the value calculated?
1
vote
1answer
68 views

Converse of the Watson's lemma

Watson's lemma basically says $$ f(t) \sim t^{\alpha} \,\,\,(\text{for small } t) \implies \int_0^{\infty} f(t) e^{-st} dt \sim \frac{\Gamma(\alpha + 1)}{s^{\alpha + 1}} \,\,\,(\text{for large } s). $...
2
votes
1answer
48 views

Could Master Theorem be applied to this recurrence relation?

I have the following recurrence relation $T(n) = 4T(\frac{n+4}{2}) + n$ Is there some way in order to apply the Master Theorem to it? Or do I have to find an alternative approach in order to solve ...
1
vote
0answers
36 views

Upper bounding a sum of products

Let $a_k$ be an integer valued sequence, $a_k \in \mathbb{N}^+$ and let $b_k = \#\{i: a_i=1,\; i \leq k\}$ and assume that $b_k=o(k)$ (little o notation). How to prove that there exists a constant $...
0
votes
0answers
25 views

Asymptotic behavior of inverse laplace transform [duplicate]

My question may be quite rough. Let $F(\lambda)$ be the Laplace transform of some function $f(t)$, $$ F(\lambda)= \int_0^\infty e^{-\lambda t}f(t) dt. $$ If I have knowledge about $F(\lambda)=O(\...
2
votes
1answer
38 views

Asymptotic lower bound of this function

Suppose that $n$ is an even number. Let $$f(n)=\frac{\sum_{j=1}^{n/2}\binom{n}{2j}\log(2j)}{2^{n-1}}.$$ Can we find some function $g(n)$ (e.g. $\log(n)$ or $n^\alpha$) such that $f(n)=\Omega(g(n))$? ...
-2
votes
2answers
54 views

Using the definition of $f$ is $O(g)$ proof: [closed]

I'm studying for my discrete math class and I don't understand how to prove big O notation. I understand that $f$ is $O(g)$ of another if $f(x) \le c g(x)$ holds. How would I go about proving $\sin ...
2
votes
1answer
73 views

Finding 8 co-primes $\le 2^n$

We can find 8 co-prime integers $\le 2^n$ for sufficiently large $n$. I'm looking for asymptotic bounds for the minimum distance away from $2^n$ we have to go before finding 8 co-primes. In other ...
1
vote
2answers
75 views

Help with a limit using big O?

$\lim_{x\to 0} \frac{4sin^{2}(\frac{x}{2})-x^{2}cos(\frac{x}{2})}{4x^{2}sin^{2}(\frac{x}{2})}$ is equal to $\frac{1}{24}$ apparently but I can't work it out. My attempt: $\lim_{x\to 0} \frac{4(\frac{...
0
votes
1answer
22 views

asymptotic notations : if $0<a<b$ then $n^b=\Omega(n^a)$

If $0<a<b$ then $n^b=\Omega(n^a)$. I have learned about this quiet recently and have come across this equation. I am having difficulty proving this. Any help would be appreciated.
0
votes
0answers
24 views

Doubts and computations about Dirichlet series and aliquot sequences I

Perhaps the more easier statement that one can deduce for aliquot sequences (which is the Wikipedia's Page) is the following Lemma. For an integer $n\geq 1$, let $s^0(n)\equiv n$, $s(n)\equiv s^1(...
6
votes
1answer
2k views

Orders of Growth between Polynomial and Exponential

What is known in contemporary mathematics about orders of growth for functions that exceed any degree polynomial, but fall short of exponential? This is a subject for which I've found little ...
0
votes
0answers
29 views

Combinatorics of classifying objects.

Given a multiset of $n$ primes (with product of multiset less than $2^{n\log n}$) how many ways can we assemble them into $k$ composite number of equal size? I am looking for asymptotics.
8
votes
1answer
241 views

How to solve the non-linear differential equation $y''=x-y^2$?

$y''(x)=x-y^2(x)$ I'm particularly interested in solutions when $x>0$. I've performed asymptotic analysis and reached the conclusion that solutions must behave as $\pm\sqrt{x}$ when $x\rightarrow ...
4
votes
4answers
109 views

Decreasing function that behaves like $1-x^2$ for small $x$ and like $e^{-x}$ for large $x$

I am trying to find a function with a domain $D = \mathbb{R}_+$, that is behaving like $1-x^2$ for small $x$ and like $e^{-x}$ for large $x$. Edit: And is monotonically decreasing. I thought about ...
0
votes
0answers
25 views

Some doubts related to Lovasz Local Lemma.

I have 2 question regarding Lovasz Local Lemma. In the book Probability and Computing: Randomized Algorithms and Probabilistic Analysis , it is shown that $Pr(\cap_{i=1}^n \overline{E_i}) \ge (1-...
1
vote
2answers
34 views

Correct order of the growth function [closed]

$5 \log( \log n) $ $n (\log n)^2$ $\sqrt{n} \log n$ $n^{\frac{4}{3}}$ $n \log (\log n)$ $7 \sqrt{n}$ What is the ascending order of the growth function? Please give the explanation as well.
1
vote
3answers
39 views

Asymptotic expansion of ratio function

I want to expand the following function: $$ f(x)=\frac{1}{(1-e^{-x})} $$ $f(x)$ can be rewritten as $$ f(x) \sim \frac{1}{x-x^2/2 + x^3/2/3} $$ But I want to express big-oh notation such that $$ f(...
0
votes
1answer
34 views

Which one grows faster?

Is the following statement true or false? $(\log n)^{10} = O(n^{0.10})$ When trying to solve this, I thought it was false, but according to my teacher's answers, it's true. I would like to know if ...
0
votes
0answers
31 views

Multiscale asymptotic expansion of differential equation with a constant

My question is: How to apply a two-time asymptotic analysis to the equation: $\frac{\partial v}{\partial t} + v\frac{\partial v}{\partial x} = \beta+\,\,\frac{d I}{d x}$ $\,\,\,\,\,\,\,\,\,\,...
2
votes
2answers
64 views

asymptotic behaviour of the integral without Laplace’s method

I don't know asymptotic behaviour of the integral $$\int_{0}^{\infty}\frac{du}{\sqrt{4\pi u^{3}}}\left(1-\frac{e^{-\Omega u}}{\sqrt{\frac{1-\exp\left(-2u\right)}{2u}}}\right),$$ when I read a physics ...
0
votes
0answers
20 views

Landau notation related question

Hi :) Just a quick question here. When you put $cos(x)$ into wolframalpha, it says that the taylor series expansion about $x=0$ is $1 - \frac{x^2}{2} + \frac{x^4}{24} + O(x^6)$. My question is, how ...
2
votes
1answer
46 views

Is $x^x$ in the same asymptotic growth class as an exponential function?

I see that for any natural number $a$, $\lim_{x\to\infty} \tfrac{x^x}{a^x}$ approaches $\infty$, so the limit does not exist. So is this function have a different big-O than $O(a^x)$, for example? So ...
0
votes
0answers
15 views

Asymptotic Solution to ODE

Suppose $a(x)\sim b(x)$ when $x\rightarrow + \infty$. When is the solution of $F(y', y, x, a(x))$ asymptotically equivalent to the solution of $F(y', y, x, b(x))$? The method of dominant balance ...
0
votes
0answers
30 views

Incomplete Gamma Asymptotics

my question is simple : if $a_n$ and $z_n$ are both real positive sequences tending to $+\infty$, what is the asymptotic ($n \to +\infty$) behaviour of $\Gamma(a_n,z_n)$ when 1) $a_n \neq z_n$ and $\...
2
votes
0answers
52 views

A Simple Stochastic Integral Asymptotics

Let $B(t)$ be the standard Brownian motion, $\mu(t,x)$ and $\sigma(t,x)$ are continuous functions, and $$dr(t) = \mu(t,r(t))dt+\sigma(t,r(t))dB(t).$$ $(\mu,\sigma)$ obeys the linear growth condition $...
1
vote
1answer
14 views

How is it true that for large $t$, $(1+O(1/t))e^{-2\ln t O(1/t)}=1+O(\ln t/t)$?

The title pretty much says it all. At some point in large time analysis, the following claim popped out but I don't see how it is true: For sufficiently large $t>0$, $$ \frac{2\ln t}{t}(1+O(1/t))e^...
0
votes
1answer
37 views

What is an accurate approximation and asymptotic for this function?

$$f(n)=\Bigg(1-\Big(1-\frac{1}{2^{n/2}}\Big)^n\Bigg)^{n^7}$$ I am interested in large $n$. The number $7$ can be replaced by any fixed integer. I have $$f(n)\rightarrow\Bigg(1-e^{-n2^{-n/2}}\Bigg)^{...