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

learn more… | top users | synonyms (1)

8
votes
3answers
249 views

Asymptotic behaviour of sum over the inverse japanese symbol

I am interested in the asymptotic behavior of the sum $$\sum_{m=1}^M\frac{1}{\sqrt{m^2+\omega}}$$ for $1>\omega>0$ in the Limit $M\to\infty$ up to order $\mathcal{O}(M^{-1})$. The first thing I ...
0
votes
2answers
31 views

Difference between the definitions regarding distribution of prime numbers

Following are the two theorems that Hardy and Wright state in their book Theorem A: The number of primes not exceeding $x$ is given by $\pi(x) \sim \frac{x}{\log{x}}$. Theorem B: The order ...
-1
votes
2answers
39 views

Solve $\sqrt{1-2x+x^2+o(x^3)}$ with $x \to 0$ [duplicate]

I need help to solve $\sqrt{1-2x+x^2+o(x^3)}$ with $x \to 0$, I do not understand when and why I should stop. Here my steps: I can use Taylor formula for $\sqrt{1+t}$ so: $$\sqrt{1+t} = 1+ \frac{t}{...
0
votes
0answers
18 views

The asymptotic behaviour of $\sum_{1\leq k\leq N-1}\int_{p_k}^{p_{k+1}}\log x d[x]$, where $p_n$ is the nth prime number

Let $p_k$ is the kth prime number and consider for $N\geq 2$ the arithmetic function $$f(N)=\sum_{k=1}^{N-1}\int_{p_k}^{p_{k+1}}\log(x) d[x]$$ where $[x]$ is the integer part function (provide us in ...
3
votes
2answers
40 views

Estimate growth of a recurrence convolution

Consider the following recurrence relation $$ a_{m+1} = (4 m + 1) \sum_{k=1}^m a_k a_{m-k+1}, \qquad a_1 = 1. $$ The first several values are $$ a_1 = 1,\; a_2 = 5,\; a_3 = 90, \; a_4 = 2665, \; a_5 = ...
1
vote
1answer
38 views

Why is the CLT stated like it is?

The CLT says that given finite variance of iid RVs, we have $$\sqrt{n}( \bar{X} - \mu) \rightarrow \mathcal{N}(0,\sigma^2),$$ but if this is true, then $\bar{X} - \mu$ should converge to $\mathcal{N}(...
8
votes
0answers
91 views

Generalizing the growth of sums of two squares

Consider the set $S$ of numbers which are the sum of two (integer) squares, and define $S(n)$ as the number of members of $S$ in $\{1,2,\ldots,n\}.$ It is well-known that $$ S(n) \sim \frac{Kn}{\sqrt{\...
0
votes
2answers
40 views

Proving $f(n)=100n+5 \neq \Omega(n^2)$

I have to prove that: $$f(n)=100n+5 \neq \Omega(n^2)$$ What I tried: let's assume that $f(n)=100(n)+5= \Omega(n^2)$. Thus, there must exist some positive constant $c$ and $n_0$ such that, $$0 \leq ...
1
vote
1answer
40 views

How many polynomials are squarefree?

Of course, this depends on the field, and how we measure "how many," but it seems I cannot find an answer to this except over finite fields. My question specifically is If we have a field $F = \...
0
votes
3answers
46 views

How do I find Big O notation for this function?

How do I find Big O notation for this function? $$ n^4+100\cdot(n^2)+50 $$ In the book I am following, I got the following solution: $n^4+100(n^2)+50 \leq 2(n^4) \ \forall \ n \geq 11$ $n^4+100(n^2)+...
1
vote
1answer
54 views

For any arithmetic progression $n \in \Bbb{N} : n \equiv b \pmod a$, the natural density is $\frac{1}{a}$?

This question comes from here (page 10). Given that $d(A) := \lim_{x\to\infty}\frac{1}{x}\sharp\{n \leq x : n \in A\}$, how do I get that: $d(n \equiv b \pmod a) = \lim_{x\to\infty}(\left [ \frac{x}...
6
votes
1answer
836 views

Can a curve be an asymptote?

$f(x)=x^3+\frac{3}{x-1}$ This was the question given to me. I replied that $f(x)$ will have only a single vertical asymptote of $x=1$. My teacher told that there'll be be two asymptotes. One is the ...
1
vote
0answers
23 views

Finding a degree-2 polynomial that sits under the Harmonic Numbers.

Does there exist a degree-2 polynomial with positive acceleration such that the real extension of the harmonic numbers surpasses it for all future values? This was too big of a title and it's a ...
2
votes
2answers
46 views

How to solve asymptotic expansion: $\sqrt{1-2x+x^2+o(x^3)}$

Determinate the best asymptotic expansion for $x \to 0$ for: $$\sqrt{1-2x+x^2+o(x^3)}$$ How should I procede? In other exercise I never had the $o(x^3)$ in the equation but was the maximum order to ...
0
votes
0answers
52 views

How much can the integrability at zero tell about the decay rate around zero?

Suppose that $g$ is a continuous, nonincreasing and nonnegative function on $(0,1)$. The question is whether one can characterize the integrability of such functions at zero by their decay rates at ...
-2
votes
0answers
11 views

Mittag Leffler Stability [closed]

How to prove "Mittag-Leffler stability implies asymptotical stability" ? What should be done? Thanks.
0
votes
0answers
40 views

Questions Concerning “Approximate Polynomials”

In this paper, I encountered the following definition: Definition 2 (Approximate Polynomial) Let $U\subset \mathbb{C}$ and $\sigma\in\mathbb{N}\cup\{-\infty\}$. A function $f\colon U\to\...
5
votes
3answers
332 views

Asymptotics for partitions of $n$ with largest part at most $k$ (or into at most $k$ parts)

Let $\bar p_k(n)$ be the number of partitions of $n$ with largest part at most $k$ (equivalently, into at most $k$ parts). Is there an elementary formula for the asymptotic behavior of $\bar p_k(n)$ ...
0
votes
0answers
25 views

Asymptotic approximation of the Barnes G function [closed]

What is the asymptotic behavior of the Barnes G function ? Thanks very much.
0
votes
3answers
20 views

Proving that $h=O(\log_2 n)$ if $h=\log_2 (n+1)$

Suppose that $h=\log_2 (n+1)$. Why is $h$ also $O(\log_2 n)$? I know the definition of big $O$ notation, and properties or logarithms, but I can't figure it out - that $+1$ is causing troubles.
1
vote
1answer
31 views

Probability that at least 2 edges of $\Gamma_{n,N}$ shall have a point in common

In the classic paper of Erdos,Renyi On the evolution of random graphs[page 7] ,it is argued that the probability that at least 2 edges of $\Gamma_{n,N}$ shall have a point in common is given by $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
66 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
37 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
61 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
665 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
50 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
63 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
343 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
50 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
37 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
31 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
56 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
64 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
43 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
33 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
23 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
37 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 ...