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
1answer
45 views

Asymptotic rendering time for koch snowflakes

I posted a similar question on stack-overflow, but this may be a more proper forum since it is more math-related than programming related: I'm currently working through the online course material for ...
0
votes
2answers
27 views

Doubts on Big O definition

I have doubts on big-o $O$. Considering two function $f$ and $g$ , if $\lim_{x\to c} \frac{f(x)}{g(x)}=l \in \mathbb{R}$ Then we say that $f=O(g)$ as $x \to c$ Is it true in general that $f=O(g) ...
2
votes
0answers
43 views

Asymptotics of recursion

suppose we have the following two sequences $$\alpha_k = (k-1)\left(1-\frac {1}{1+(k+1)l}\right) \quad , k \geq 2$$ $$\beta_k = (k-1)\left(1+\frac {1}{1+(k-1)l}\right) \quad , k \geq 2$$ where ...
0
votes
0answers
27 views

If $f(n) = \Theta(n^{\log_b{a}}\lg^k{n})$ where $k \ge 0$ , then the master recurrence has solution $T(n) = \Theta(n^{\log_b{a}}\lg^{k+1}n) $.

I'm working through problems to the book "introduction to algorithms". I'm going through the section on the master recurrence and have been running into some roadblocks. I found a solution to the ...
2
votes
1answer
27 views

What can we say about the set of asymptotic equivalence classes of sequences?

Say that $$A := \{f : \mathbb{N} \to \mathbb{R}\}/\sim$$ where $f \sim g$ if $f$ and $g$ are asymptotically equivalent. That is, let $A$ be the set of asymptotic equivalence classes of real ...
4
votes
2answers
2k views

Recurrence $T(n)=T(n/2)+2^n$ and $T(n)=T(n/2+\sqrt n)+\sqrt{6044}$ , without (!) the master method

Given the Recurrences $$T(n)=T(n/2)+2^n$$ and $$T(n)=T(n/2+\sqrt n)+\sqrt{6044}$$ Remark : $T(n)=1$ for $n\le 3$ I'm trying to find their upper bound & lower bound , which is probably $O(2^n)$ ...
1
vote
1answer
34 views

$lim_{x\to c}f(x)-g(x)$ and asymptotic equivalence

I'm confused about asymptotic equivalence. I read on a textbook that, supposing $lim_{x\to +\infty} f(x)=+\infty$, $lim_{x\to +\infty}f(x)-g(x)= l \in \mathbb{R} \implies f(x) \sim g(x) $ Is this ...
12
votes
1answer
165 views

Asymptotics for a series of products

I am trying to solve the following problem: Define the following functions for $x>0$: $$f_n(x):=\prod_{k=0}^{n}\frac{1}{x+k}$$ Show that the function ...
1
vote
0answers
30 views

How to read notation about little o notation

On page 2 of this pdf the author introduces this equivalence relation: $$f(x) \sim_{x_0} g(x) \iff f(x) - g(x) = o(x-x_0)\quad \text{as } x\to x_0$$ Assuming this is a standard notation, how does ...
5
votes
2answers
61 views

$\lim_{x \to c} f-g=0\iff f \sim g$?

Considered two functions $f$ and $g$ (with $g\neq 0 $ near a point $c$) $$\lim_{x\to c} \frac{f}{g}=1 \iff f \sim g$$ I'm trying to understand if it is true that $$\lim_{x\to c} \frac{f}{g}=1 \iff ...
3
votes
2answers
112 views

Asymptotics of the differences between successive zeta zeros

Does anyone know what the asymptotic of the differences between successive zeta zeros is? Update It appears that $\zeta(n)$ is not a bad asymptotic, when the data range is stretched: ...
0
votes
0answers
21 views

Difference between being asymptotic and equivalent?

I can't understand the difference between these two definitions A function $f$ is said to be asymptotic to a function $g$ as $x \to +\infty$ if $lim_{x\to +\infty} f(x)-g(x)=0$ That means ...
4
votes
3answers
105 views

Asymptotic expansion at order 2 of $\int_0^1 \frac{x^n}{1+x} \, dx$

I'd like to get an asymptotic expansion of $\int_0^1 \frac{x^n}{1+x} \, dx$ at order two in $\frac{1}{n}$. I'm able to prove that $$\lim\limits_{n \to \infty} n \int_0^1 \frac{x^n}{1+x} \, dx = ...
9
votes
1answer
136 views

Integral Asymptotics for inhomogenous phase

I'm looking for asymptotics for an integral of the form: $$F(n):=\int_{1/2-i\infty}^{1/2+i\infty} e^{\phi(n,z)}dz$$ where $\phi(n,z)=(n-n^3)\log(1-z)+n^2\log(1+z)-n\log(z)$. One can solve for the ...
8
votes
3answers
78 views

Prove that $\cosh^{-1}(1+x)=\sqrt{2x}(1-\frac{1}{12}x+\frac{3}{160}x^2-\frac{5}{896}x^3+…)$

How can we prove the series expansion of $$\cosh^{-1}(1+x)=\sqrt{2x}\left(1-\frac{1}{12}x+\frac{3}{160}x^2-\frac{5}{896}x^3+...\right)$$ I know the formula for ...
3
votes
0answers
29 views

What is $\|\Phi x\|_2^2$ given that $\Phi\in R^{d\times d}$ is an $m$-dimensional orthogonal projection matrix uniformly drawn at random?

The problem is extracted from Page 3 and Section 6.2 of Page 15 in the paper http://arxiv.org/pdf/1506.00898v2.pdf , and here I have listed all the information I can get through the whole paper. The ...
1
vote
2answers
54 views

Deciding $\displaystyle o,\omega,\Theta$ notations

I have a question which I couldn't solve for about two hours. It goes like this: Let $\displaystyle f(n)=\left(\frac{n+3\ln(n)}{n}\right)^n \ ; \ g(n)=27^{\ln(n)}$. Fill the blank box with ...
1
vote
2answers
45 views

$2^{O(\log \log n)} = O(\log n)$ prove or disprove

I need to prove or disprove this: $$2^{O(\log\log n)} = O(\log n)$$ I haven't found anything like that through search. I would like to have some help. Thanks.
6
votes
1answer
136 views

Growth of $n!!\dots !$

The asymptotic growth of the factorial function $n!$ is famously given by Stirling's formula as $$n! \sim \sqrt{2 \pi n}\left(\frac{n}{e}\right)^n$$ Is there a similar formula for the iterated ...
1
vote
1answer
19 views

Behaviour a function when input is small

If I have the function: $P(N)=\frac{P_0N^2}{A^2+N^2}$, with $P_0, A$ positive constants For small $N$, am I right in thinking that because $A$ dominates $N$ we have that $P(N) \approx ...
2
votes
0answers
46 views

Is Stirling's Approximation used here, to prove the asymptotic inequalities?

Define $N_c=[\dfrac{1}{2}n\log n+cn]$ where $[.]$ denotes the greatest integer function, and $c$ is any arbitrary fixed real constant. Also, let $M={n\choose 2}$. Then prove, for large $n$, ...
2
votes
3answers
100 views

Upper bound for the sum $ \sum_{k=1}^N \frac{1}{\varphi(k)}$

Is there an upper bound for the sum $$ \sum_{k=1}^N \frac{1}{\varphi^{\alpha}(k)} $$ where $\varphi(n)$ is the Euler totient function and $\alpha\geq 1$ a real constant? In particular, I'm interested ...
4
votes
1answer
84 views

What is known about the 'Double log Eulers constant', $\lim_{n \to \infty}{\sum_{k=2}^n\frac{1}{k\ln{k}}-\ln\ln{n}}$?

The Euler constant is defined as $$\gamma = \lim_{n \to \infty}{\sum_{k=1}^n\frac{1}{k}-\ln{n}}$$ Let $$q = \lim_{n \to \infty}{\sum_{k=2}^n\frac{1}{k\ln{k}}-\ln\ln{n}}$$ I managed to prove that ...
2
votes
1answer
20 views

Marginal convergence in distribution implies joint convergence of a subsequence?

Consider two sequences of real-valued random variables defined on the probability space $(\Omega, \mathcal{F}, \mathbb{P})$, $X_n:\Omega\rightarrow \mathbb{R}$ and $Y_n:\Omega\rightarrow \mathbb{R}$. ...
0
votes
0answers
62 views

Asymptotics relationship from algebric identity?

Background We start with the identity: $$ \sum_{r=1}^n r \ln r + \ln (r-1)! = n\ln n! $$ $$ \implies \sum_{r=1}^n \frac{r}{n} \ln r + \frac{1}{n} \ln\Gamma(r) = \ln n!$$ $$ \implies ...
1
vote
1answer
39 views

Generalised version of le Cam's Third Lemma

I'm confused with the generalised version of Le Cam's Third lemma presented in Theorem 6.6 of van der Vaart asynptotics Statistics here: ...
14
votes
4answers
1k views

Euler's Constant: The asymptotic behavior of $\left(\sum\limits_{j=1}^{N} \frac{1}{j}\right) - \log(N)$

I want to show that there exists a constant $\gamma\in\mathbb{R}$ such that $$ \sum_{j=1}^N \frac1{j} = \log(N)+\gamma+O(1/N). $$ I know how to prove that the Euler-Mascheroni constant exists ...
1
vote
0answers
27 views

Binomial square sum and product

Given $c,n\in\Bbb N$ what is the expression for $$S(n,c)=\binom{n}c^2+\binom{n-c}c^2+\dots+\binom{x}c^2$$ and $$P(n,c)=\binom{n}c^2\cdot\binom{n-c}c^2\cdot\dots\cdot\binom{x}c^2$$ where $x-c<c\leq ...
2
votes
2answers
112 views

Asymptotic estimate of $\binom nk$

Prove: when $n\to \infty$, we have $$\sum_{k=1}^n\frac1{k^a}\binom nk\sim \frac{2^{n+a}}{n^a},$$ where $a$ is a constant. This problem is hard to me, I have no idea.
2
votes
0answers
70 views

An asymptotic estimate involving the Gamma function

In one of the lecture notes I've found that $C_n$ $$ C_n= \begin{cases} \frac{n!}{\sqrt 2 \Gamma((n/2+1)}\pi^{-1/42^{-n/2}(n!)^{-1/2}} & n\text{ even} \\[4mm] \frac{2(n!)}{(\sqrt2n+1/(\sqrt2 ...
1
vote
1answer
14 views

Relationship between short-time and large-frequency asymptotics in Fourier transform

I am trying to understand how the short-time behaviour of a function $f(t)$ influences the large-frequency asymptotics of its Fourier transform $g(\omega)=\mathcal{F}[f(t)](\omega)\equiv ...
2
votes
1answer
25 views

Assymptotics of the generalized harmonic number $H_{n,r}$ for $r < 1$

The $H_{n,r}$ generalized harmonic number is defined as: $$H_{n,r} = \sum_{k=1}^{n} \frac{1}{k^r}$$ I'm interested in the growth of $H_{n,r}$ as a function of $n$, for a fixed $r\in[0,1]$. For ...
6
votes
2answers
88 views

Is there standard terminology to describe the not-quite-a-limit behavior of ${\tan( \log x) \over x}$ as x approaches infinity?

Suppose I want to describe the long term behavior of ${\tan(\log x) \over x}$ as x increases towards positive real infinity. Now, $$\lim_{x \rightarrow \infty}{\tan(\log x) \over x}$$ obviously ...
1
vote
1answer
29 views

Is the function $f(x)$ uniformly continuous on $(0, 1)$ if (a) $f(x) = x\sin(x^{-2})$ and if (b) $f(x) = \sin(x^{-2})$?

Is the function $f(x)$ uniformly continuous on $(0, 1)$ if (a) $f(x) = x\sin(x^{-2})$ (b) $f(x) = \sin(x^{-2})$ I have been using big O notation to try to solve this - since $$\sin(u) = u- ...
1
vote
0answers
33 views

Asymptotic of $ _1F_1(a;b;z)$

How it can be shown that $$ _1F_1(a;b;z) = \frac{\Gamma(b)}{\Gamma(a)}\, e^{z} \, z^{a-b}\, [1+ O(\mid z\mid^{-1})]; \quad (\Re(z)>0)$$ or $$ _1F_1(a;b;z) = \frac{\Gamma(b)}{\Gamma(b-a)}\, ...
0
votes
3answers
28 views

How is Big-O notation used in equalities?

I recently learned about big-O notation and I think I get it but in some uses it does not line up with what I think I understand it as. In the wikipedia page it calls using the form $f(x) = O(g(x))$ ...
1
vote
1answer
27 views

Find the asymptotical distribution of maximum likelihood estimator $\hat \theta$?

Assume $X_1, X_2,\ldots,X_n$ are iid with pdf $f(x \mid \theta)=\frac{\theta^2}{2} e^{-\theta^2 \|x\|}$, $x \in \mathbb R$, where $\theta > 0$ is an unknown parameter. First, find mle $\hat ...
8
votes
1answer
126 views

How to estimate solutions to an ODE with an asymptotically nilpotent coefficient?

Suppose $f:\mathbb R\to\mathbb R^n$ satisfies $$ f'(t) = A(t)f(t), $$ where $A$ is a smooth matrix-valued function. If I know that the matrix $A(t)$ is asymptotically nilpotent, how could I prove a ...
4
votes
3answers
84 views

Series expansion of integral

Consider the function $I(y)=\int_0^\infty e^{-\sqrt{x^2+y^2}} \mathrm{d} x$. I'd like to see the leading order term of $I(y)$ about $y=0$, so I expand the integrand: $$ ...
0
votes
0answers
27 views

Chromatic number of random graph

Building random graph with probability to connect two vertex $p = \frac{1}{2n}$, and not connect $q = 1 - \frac{1}{2n}$. Find chromatic number a.a.s.(asymptotically almost shure), when $n$ tends to ...
0
votes
2answers
79 views

Let $f(n) = 2n^2 + 7n − 1$. Show that $f = O(n^3)$

The book I'm using states that a function $f$ is $O(g)$ if there exists a positive constant $C$ and a positive integer $k$ such that $$f(n)\le Cg(n)$$ for every integer $n\ge k$. How do I use the ...
0
votes
1answer
66 views

Big O notation - proving the relationship

Suppose that $n=O(\log_2 m)$. Let $f=O(m)$. How can we prove that $f=O(2^n)$ as well? I know that $m=2^{\log_2 m}$, but I can't simply plug $n$ there, because $n$ isn't equal to $\log_2 m$, but ...
1
vote
1answer
21 views

Applications of Prohorov's Theorem

Consider the sequence of real-valued random variables $\{X_n\}_n$ and suppose it converges in distribution to $V$. Does this imply that (1) every subsequence of $\{X_n\}_n$, $\{X_{n_k}\}_k$ ...
0
votes
1answer
57 views

Does it have a valid mathematical meaning?

Does the following expression: $$2^{O(\log m)}$$ have any mathematical meaning? Is it even correct to write this? I have certain doubts. $O(\log m)$ is not a well-defined number, so it's difficult ...
3
votes
1answer
30 views

How do you solve the recurrence relation $T(n) = cn(dn + T(n-k))$?

How do I come up with a big-O approximation to $T(n) = cn(dn + T(n-k))$ where $c, d \in \Bbb{R}$ are fixed. $T(n)$ is the running time of a recursive algorithm. This seems difficult as usual. :)
2
votes
2answers
58 views

Can you give a closed form or an asymptotic for $\sum_{m=0}^{k-1}\cos(\frac{2\pi m n}{k \log 2})$ for $k\to\infty$?

I want compute, in a closed form or an asymptotic (with a, big oh as, error term) this mean $$\delta_k(n):=\sum_{m=0}^{k-1}\cos(\frac{2\pi m n}{k \log 2})$$ defined for each integer $k\geq 1$. ...
3
votes
2answers
63 views

What is the closed form approximation of the asymptotic growth rate of the superfactorial function?

The asymptotic growth rate of the hyperfactorial function (defined to be: $H(n)=\prod^n_{k=1}k^k$) is apparently (approximately) equal to: I'm curious as to how this result is obtained, and am ...
1
vote
1answer
60 views

Behaviour of modified Bessel function of the second kind $K_{\nu}(x)$

The modified Bessel function of the second kind $K_{\nu} (x)$ should have an exponential - decreasing - behaviour with respect to its variable $x$, as shown in this document (page 19, fig. 4.4). As ...
3
votes
0answers
25 views

A sequence converging to 0 in probability times a sequence bounded in probability

I'm trying to prove the following from Lehman's "Elements of Large Sample Theory" Lemma 2.3.1: If the sequence $\{Y_n, n=1,2,\ldots\}$ is bounded in probability and if $\{C_n\}$ is a sequence of ...
0
votes
0answers
24 views

Modified Bessel functions with negative argument

As recalled in a previous question, the modified Bessel functions of the first and second kind $I_{\nu}(x)$ and $K_{\nu}(x)$ can be obtained from $J_{\nu}(ix)$ and $N_{\nu}(ix)$: that are the Bessel ...