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

Asymptotic behavior of zeros of a function

Let $f(x,m)=(2m-1)\Gamma(m)\,x^{-m}$ where $x>0$ and $\Gamma(z)$ denotes the Gamma function. Let $g(x,m)=f(x,m)+f(x,-m)$. I'm interested in the solution $m=m(x)>0$ of the equation $g(x,m)=0$ ...
4
votes
0answers
71 views

Asymptotic Expansion for an Integral

So I have $$\psi(x)=\int_{2\lambda}^x \frac{(e\lambda)^{z}}{z^{z+1/2}} dz$$ I'm trying to find the asymptotic expansion of $\psi(x)$ as $x \to \infty$ for as many orders as possible. How would I go ...
0
votes
1answer
36 views

Proving Gale-Shapley algorithm completes in $O(n^2)$

In Algorithm Design by John Kleinberg and Eva Tardos, the proof for the Gale-Shapley algorithm running in $O(n^2)$ is given In the case of the present algorithm, each iteration consists of some ...
0
votes
0answers
49 views

consider the function $f(1) = 1$, $f(n) = \sum_{i = 1}^{n - 1}(if(i))$ for $n > 1$

Consider the function $f(1) = 1$ $f(n) = \sum_{i = 1}^{n - 1}(if(i))$ for $n > 1$ Let $A(n)$ be the worst-case number of scalar arithmetic operations (+,-,*,/) required by this function for ...
1
vote
0answers
17 views

Can you discuss $\limsup_{n\to\infty}\frac{g_n}{\log^2p_n}\cdot\frac{\sigma(K_n)}{K_n\cdot\log\log K_n}$, where $g_n=p_{n+1}-p_n$ and $K_n\to\infty$?

Let $p_n$ the nth prime number, then we know that the nth gap is $g_n=p_{n+1}-p_n$. We define for $n>1$, $C_n$ as the set of integers such that $gcd(k,p_{n+1})=gcd(k,p_{n})=1$, this is $\{1\leq k ...
1
vote
1answer
22 views

Give a big-O estimate of $(x+1)\mathrm{log}(x^2+1) + 3x^2$

I wanted to know if the following solution demonstrates that the function $f(x) = (x+1)\mathrm{log}\, (x^2+1) + 3x^2 \in O(x^2)$, because my answer and the book's answer deviate slightly. Clearly, ...
0
votes
0answers
23 views

Questions about $w(\prod_{k=1}^{n}(p_{k}-1))-w(\prod_{k=1}^{n}(p_{k}+1))$

Let's define this functions. $$f(n)=\prod_{k=1}^{n}(p_{k}-1)$$ $$g(n)=\prod_{k=1}^{n}(p_{k}+1)$$ $$h(n)=\mid w(f(n))-w(g(n))\mid $$ where $p_{k}$ is $k$th prime number and $w(n)$ gives the number of ...
1
vote
1answer
39 views

What is the order of the quantifiers in the definition of big-O?

Suppose $f$ and $g$ are functions. I am pretty sure that the definition of big-O has its definition conform to the following logical structure $$\exists \, k \, \exists C \, \forall \,x\, :\, x > ...
4
votes
3answers
88 views

Asymptotic formula for $\prod_{k=1}^{\infty}\zeta (2kn)$

Suppose $n\geq 1$ is a positive integer. Can we find an asymptotic formula for this product below. $$\prod_{k=1}^{\infty}\zeta (2kn)=\zeta (2n)\zeta (4n)\zeta (6n) \cdots$$ I tried to use $\zeta ...
1
vote
0answers
25 views

How many binary polynomials of degree <2n-1 are the the product of polynomials of degree <n?

Let $P_n$ be the set of all polynomials over $\mathbb{Z}_2$ and of degree less than $n$. What is the rate of growth of $|\{x y : x,y \in P_n \}|$? I'm looking for an answer like "$\Theta(2^{3n/2})$" ...
2
votes
2answers
41 views

Big O - equivalent definitions

A function $f(x)$ is $O(g(x))$ if and only if there exists a real number $M$ such that there exists $x_0$ such that for every $x>x_0$ the inequality $|f(x)|\le M|g(x)|$. It turns out the following ...
4
votes
4answers
160 views

How to show $\zeta (1+\frac{1}{n})\sim n$

How to show $\zeta (1+\frac{1}{n})\sim n$ as $n\rightarrow \infty$ where $\zeta$ is the Riemann zeta function. And can we say $\lceil \zeta (1+\frac{1}{n}) \rceil=n$ for any positive integer $n\geq ...
1
vote
0answers
36 views

Book Recommendations on Perturbation Theory

I am interested in studying Quantum Electrodynamics and figure I should begin by learning Perturbation theory and Asymptotic expansions. If anyone could recommend some books, that would be very ...
1
vote
1answer
49 views

Can I say $\log{O(n)}$?

Suppose $e^{f(x)} = O(x)$, or equivalently, there exists a $c$ such that for all $x$, $f(x) \lt \ \log{x} + c$. Is $f(x) = \log{O(x)}$ generally understood to mean the same thing?
0
votes
2answers
34 views

Finding the least integer n for a function Big-O of another function?

I was out all last week sick with the flu and am trying to get caught up in my Discrete Mathematics course. One set of questions in my book goes as follows: Find the least integer $n$ such that $f(x) ...
0
votes
0answers
17 views

It is possible an application of Shapiro's Tauberian theorem for $\sum_{n\leq x}\frac{|M(n)|^{1+\alpha}}{\pi(n)^{1+\beta}}\left[\frac{x}{n}\right]$?

I would like to know if I can find some $\alpha,\beta\geq 0$ such that defining the sequence $a(1)=1$ and for $n>1$ as $$a(n)=\frac{|M(n)|^{1+\alpha}}{\pi(n)^{1+\beta}},$$ where $M(n)=\sum_{k\leq ...
0
votes
0answers
20 views

Big-O Notation and showing algorithmic growth rate with witnesses?

I have been out of class sick for a week with the flu and am having some trouble getting caught up on our latest sections on Big-O notation. Can someone explain the following from the textbook to me? ...
0
votes
2answers
42 views

Errors in our estimation of a function- and what does big-O notation have to do with it?

We're given the function $f(x) =e^x$ and we're trying to estimate its second derivative at $x=0$. Here's the estimation formula. $$f''(x)\approx {f(x) - 2f(x+h) + f(x+2h)\over h^2}= P(x)$$ All three ...
2
votes
1answer
54 views

Evaluating $\lim_{x\to\infty}\frac{1}{x}\int_2^x M(t)\cdot f'(t)dt$, where $M(x)$ is Mertens functions

Let $\mu(n)$ the Möbius function. I know that combining Abel summation formula, the Prime Number Theorem and l'Hôpital's rule I can deduce $$\lim_{x\to\infty}\frac{1}{x}\sum_{2\leq n\leq ...
1
vote
1answer
12 views

Asymptotic Relative Efficiency of Sample Mean and Median

I'm following some online lecture notes on AREs and don't understand where a certain value came from. Consider a distribution function $F$ with a density function $f$ symmetric about $\theta$. We're ...
0
votes
3answers
34 views

Show $\lim_\limits{n\rightarrow \infty} \sqrt{n}(|c+\frac{d}{\sqrt{n}}|-|c|) = d* sign(c)$

Consider the sequence of real numbers $\sqrt{n}\left(\left|c+\frac{d}{\sqrt{n}}\right|-|c|\right)$ with $c,d \in \mathbb{R}$ and $c\neq 0$. Could you help me to show that $$\lim_\limits{n\rightarrow ...
5
votes
1answer
133 views

The function $\mathrm{Li}_2(x)=\int_2^x\frac{dt}{\log^2t}$, its inverse and summation

I am reading the more understandable mathematics in the section Preliminary Results of a paper in which the authors give a explanation of facts for the logarithmic integral and its inverse. In this ...
0
votes
0answers
15 views

Show that the point of minimum of a random function is bounded in probability

Consider a sequence of random variables $X_n:\Omega \rightarrow \mathbb{R}^k$ defined on the probability space $(\Omega, \mathcal{F}, P)$. Consider a parameter $\theta \in \Theta \subseteq ...
1
vote
0answers
28 views

Instantaneous drift of a stochastic process

Let $\mu_t$ and $\sigma_t$ be strictly positive bounded predictable processes and $W_t$ a Wiener process. Consider for $\Delta>0$ $$ X_{\Delta} = ...
0
votes
2answers
43 views

Almost sure convergence along a subsequence implies convergence in probability over the whole sequence

Consider a sequence of real-valued random variables $\{X_n\}_n$ almost surely converging to a real-valued random variable $X$ along a subsequence $\{n_k\}_k \subseteq \mathbb{N}$: $X_{n_k} ...
1
vote
1answer
44 views

A didactic example of logarithmic measure

I've read that two mathematicians, in the recent past, studied limits as $X$ tends to infinite, like as $$\frac{1}{\log X}\sum_{x\leq X:\pi(x)<\int_{2}^x\frac{dt}{\log t}}\frac{1}{x},$$ where ...
0
votes
0answers
29 views

Asymptotics of $\sum_{x = 0}^{\alpha n} {n \choose x}$

Let $\alpha \in (0, 1)$. What is the asymptotic growth of the following function? $$\sum_{x = 0}^{\alpha n} {n \choose x}$$ I am aware that ${n \choose \alpha n}$ grows asymptotically as a ...
0
votes
1answer
44 views

What does the ' symbol mean in this context?

This pertains to an explanation of Big-O notation: If one pair of witnesses is found, then there are infinitely many pairs. We can always make the k or the C larger and still maintain the ...
0
votes
0answers
15 views

On an asymptotic recurrence

Fix $c\in\Bbb R$. Denote $A_0=M_0=n$. Consider $A_{i+1}=A_i+\lceil A_i^c\rceil$ and $M_{i+1}=M_i\times \lceil M_i^c\rceil$. How fast does $A_i$ grow for different ranges of $c$? $M_i$ grows as ...
2
votes
2answers
61 views

Finding asymptotic relationship between: $\frac {\log n}{\log\log n} \overset{?} = (\log (n-\log n))$

Given $f(n)=\frac {\log n}{\log\log n} , g(n)= (\log (n-\log n))$, what is the relationship between them $f(n)=K (g(n))$ where "K" could be $\Omega,\Theta,O$ I thought of taking a log to both ...
2
votes
1answer
57 views

A strange identity related to the imaginary part of the Lambert-W function

Working on a problem in QFT, i was stumbeling about some expressions containing the Lambert-$W$ function. Playing around, i discovered experimentally that the following statement seems to be true ...
1
vote
0answers
53 views

Can you estimate the difference of primes between numerator and denominator?

Let $p_n$ the nth twin prime, it is $p_n$ is a prime number and $2+p_n$ is also a prime. It is well know that Brun's theorem states (unconditionally) that $$\mathcal{B}=\sum_{n\geq ...
9
votes
0answers
100 views

Eigenvalue problem for $−\psi''(x) − (ix)^ N \psi(x) = E\psi(x)$ in complex plane

To find the eigenvalue $E$ in the complex plane of $x$ for one dimensional Schrodinger equation $$ −\psi''(x) − (ix)^ N \psi(x) = E\psi(x). $$ where $N$ can be any real number, the boundary condition ...
1
vote
2answers
25 views

Big-oh and Small-oh Notation: Ratio.

Is it possible to say something about the order of ratios like $O(1/n^2)/o(1)$ or $O(1/n^2)/O(1/\sqrt{n})$?
0
votes
1answer
31 views

does $f(n) = O(g(n))$ implies $(f(n))^{log(n)} = O((g(n))^{log(n)}) ?$

if $f(n)$ and $ g(n)$ are monotonically increasing, and $f(n) = O(g(n))$. Does it imply that $(f(n))^{log(n)} = O((g(n))^{log(n)}) ?$ Well I had a go at it saying I need to show that ...
2
votes
4answers
49 views

Showing that Harmonic numbers are $\Theta(\log n)$, intuitively

I wish to verify that Harmonic numbers $H_n = \sum_{k=1}^{n} \frac{1}{k}$ are $\Theta(\log n)$. One idea I have is to approximate the sum with an integral: $$\int_{1}^{n} \frac{1}{k} ~dk = \log(n) - ...
1
vote
2answers
49 views

Big O notation: ratio of two $O(\cdot)$'s is $O(\cdot)$ of the ratio?

Is it true that if $f_1=O(g_1)$ and $f_2=O(g_2)$ then $$\frac{f_1}{f_2}=\frac{O(g_{1})}{O(g_{2})}=O\!\left(\frac{g_1}{g_2}\right)$$ ?
2
votes
0answers
44 views

Asymptotic behaviour of an integral depending on a parameter

I am trying to compute the asymptotics on $t$ of the following integral: \begin{equation} I(t)=\int_{\mathbb{R}^{n}}e^{-|\lambda|^{2}/2t}\prod_{i<j}\left( e^{\lambda_{j}/t}-e^{\lambda_{i}/t} ...
4
votes
1answer
33 views

What about $\sum_{\substack{2\leq n\leq y,\text{n prime}}}n\log\log n$ when $y=[x]\to\infty$?

For a real $x\geq 2$ and when we take $y= [x]$ its integer part, I am trying to study the asymptotic size or growth of $$\sum_{\substack{2\leq n\leq y,\text{n prime}}}n\log\log n,$$ I believe that ...
0
votes
1answer
13 views

How to get values of $n_0$ and $c$ for big-omega.

Let $f(n)=3n^3$ and $g(n) = n^3$ then $f = Ω(g)$ Answer: Let $n_0 = 0$ and $c = 1$ So I know how to find $c$ and $n_0$ for big-oh, like this: $3n^3 \leq cn^3$ [divide to be left with c] $= c ...
1
vote
0answers
29 views

Approximating $\prod_{r=s}^t (1-b/r)$

I am currently trying to place an order of precision on the approximation $$\prod_{r=s}^t \left(1-\frac{b}{r}\right) \approx \left(\frac{s}{t}\right)^b$$ This follows because $$\prod_{r=s}^t ...
0
votes
0answers
14 views

Derive the asymptotic distribution of $\frac{2}{n(n-1)}\sum\sum_{i<j}|X_{i}-X_{j}|$

Derive the asymptotic distribution of Gini's mean diference, which is defined as $\frac{2}{n(n-1)}\sum\sum_{i<j}|X_{i}-X_{j}|$. This is an exercise of Asyptotic Statistics by A.W. van der Vaart. I ...
1
vote
0answers
34 views

Asymptotic sums and big-O notation

Suppose I have to compute the following asymptotic sum ($x\rightarrow\infty$): $$ S(x):=\sum_{n\leq f(x)} O(g(x,n))\;, $$ where the function $g(x,n)$ is non-decreasing in $n$, so that in our case ...
0
votes
0answers
15 views

mann's test for trend

To test the null hypothesis that a sample $X_{1},...,X_{n}$ is i.i.d. against the alternative hypothesis that the distributions of the $X_{i}$ are stochastically increasing in $i$. Mann suggested to ...
9
votes
3answers
203 views

Finding where the tail starts for a probability distribution, from its generating function

Suppose we generate "random strings" over an $m$-letter alphabet, and look for the first occurrence of $k$ consecutive identical digits. I was with some effort able to find that the random variable ...
0
votes
1answer
25 views

Find the asymptotic solution $\Theta$ of the recurrence using the master theorem

I just took a quiz for an algorithms class that I didn't do so well on. It was on the master theorem. Unfortunately the professor refuses to supply answers or even tell me what I got wrong, so I was ...
2
votes
2answers
22 views

Comparing the growth of two function by taking logarithms

I was trying to understand how to compare the big-O growth of two functions by taking the logarithm (or some increasing function like $\sqrt{f(n)}$. For example, take $2^{({log_2n})^2}$ vs $ ...
0
votes
0answers
26 views

Growth rate of $\zeta(n)^{-1}$

What is the asymptotic growth rate of $\frac1{\zeta(n)}$? Is it polynomial in $n$?
0
votes
2answers
45 views

Prove or disprove that $\forall n \in N$ $, \, n! \in \mathcal{O}(2^n)$

Prove or disprove that $\forall n \in N$ $, \, n! \in \mathcal{O}(2^n)$ My attempt: $f(n) = n!$ $g(n) = 2^n$ First I checked if I needed to prove or disprove this statement, and to do so I ...
2
votes
1answer
50 views

Master method and choosing $\epsilon$

I am reading CLRS3, currently Chapter 4 and Section 4.5, "The master method for solving recurrences." I understood what is the $\epsilon$ , but I can't understand why they choose $ \epsilon ...