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

learn more… | top users | synonyms (1)

2
votes
0answers
30 views

Asymptotic vlaue of $ f(n)=\sum_{i=0}^n\lfloor \sqrt{i}\rfloor\binom{n}{i} $

Inspired by this question I tried to find an asymptotic formula for $$ f(n)=\sum_{i=0}^n\lfloor \sqrt{i}\rfloor\binom{n}{i} $$ With the observation: $$ f(n)=\sum_{i=0}^n\frac{\lfloor \sqrt{i}\rfloor+\...
1
vote
2answers
17 views

Growth function and one misunderstanding point?!

I have a question about Growth and Asymptotic notation topic. My question is as follows: $2^n$ > $n^{log_2{(n)}}$ is True. anyone could say how we can deduce that this fact is true?
0
votes
1answer
23 views

Big O notation for summation function

May be I am missing something very simple but I am finding it hard to understand why Big O for summation is O(n^2). I know that Big O for summation comes from fact that sum(1 to n) = n(n+1)/2. But if ...
0
votes
1answer
36 views

Would these witnesses satisfy this big-O function?

I'm trying to determine if $f(x) = \lceil x/2 \rceil$ is $O(x)$. I know that this is true, and the textbook answer is: $|\lceil x/2\rceil|\leq |(x/2)+1| \leq C|x|$ for all $x > 2$, with ...
0
votes
0answers
29 views

How do you solve the following questions on asymptotic analysis. Please share your approach. [on hold]

Check this image: I have read about the three notations but I'm unable to use the concepts to solve questions like this.
1
vote
2answers
207 views

Does $f(\epsilon)=o(\epsilon\ln(\epsilon))$ imply $\frac{f(\epsilon)}{\epsilon}=o(1)$?

I have the following homework question: Does $f(\epsilon)=o(\epsilon\ln(\epsilon))$ imply $\frac{f(\epsilon)}{\epsilon}=o(1)$ ? It doesn't seem correct to me, using the definition I could only ...
0
votes
1answer
13 views

Summation with Floor and Square Root functions + Tight Bounds

I was applying a methodology that allows to come up with iterative algorithms time-complexity function's closed-form. I ran into a particular where I ended up with the result below. I wouldn't have ...
0
votes
1answer
18 views

Necessary and/or sufficient conditions for summability of a sequence

It is clearly true that any $(a_n)_{n=1}^\infty$ that has $$a_n=O(n^{-1-\varepsilon}),$$ for some fixed $\varepsilon>0$, is absolutely summable: $$\sum\limits_{n=1}^\infty |a_n|<\infty.$$ My ...
0
votes
0answers
21 views

numerical integration asymptotic relation

Let $Q\subset R^n$ be a convex subset and $f\in C^2(Q)\;$ We set $x_s:=\int_Q xdx$,$\;\;\;Vol(Q):=\int_Q 1dx$ and $diam(Q)=sup||x-y||_2$ Prove the following asymptotic relationship: $...
12
votes
4answers
238 views

An equivalent for $\sum_{n=0}^{\infty} e^{-x\sqrt{n}}$ as $x$ tends to $0^+$

I would like to obtain an equivalent form for $$ f(x)=\sum_{n=0}^{\infty} e^{-x\sqrt{n}} $$ as $x \rightarrow 0^+$. I tried without success to "remove" the $\sqrt{\cdot}$ in the summand by summing ...
8
votes
3answers
263 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
36 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
40 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}{...
1
vote
0answers
26 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
41 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
93 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
42 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
837 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
56 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 ...
1
vote
0answers
44 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
3answers
21 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
666 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
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
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^...