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

Why can't this be done with Master Theorem

Apparently recurrences like this cannot be solved with the Master Theorem: $T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log(n)}$ Because $n^{\log_b(a)} = n^1$ is not a polynomial multiple of $f(n) ...
0
votes
0answers
10 views

Give an example of a function R with $R(h) = 0(\lVert X_n\lVert)$ as $h\to 0$ such that $R(X_n) \neq o_p(X_n)$

There is a lemma in a book of Asymptotic Statistics. 2.12 Lemma. Let R be a function defined on domain in $R_k$ such that $R (0) = 0$. Let $ X_n $ be a seq. of r.vectors that converges to zero in ...
1
vote
2answers
41 views

How to analyze the time complexity $\Theta$ of this recurrence

I am trying to understand how to show that $$T(n) = T(n/2) + T(n/4) + n^2$$ is $\Theta(n^2)$ by using a recursion tree. I tried substitution at first but it got real messy real fast. This is ...
0
votes
1answer
34 views

how far $2k+log_2(k+1)$ is to $k+log_2(k)$

Given two functions $f(k)=2k+log_2(k+1)$ and $f'(k)=k+log_2(k)$, I am wondering how far $f(k)$ is to $f'(k)$ in asymptotic notation. If $k$ is large then $log_2(k)\approx log_2(k+1)$ and ...
1
vote
1answer
39 views

Why does the Master Theorem work for this example but not the other?

So apparently: $T(n) = 2T(n/2) + n / \log n$ doesn't work with the Master Theorem because of the log term. But then: $T(n) = 4T(n/2) + n / \log n$ is $\Theta(n^2)$ even though it's still the same ...
1
vote
1answer
39 views

How to prove that $log(f(x)) \sim log(g(x))$

Considering two functions $f(x)$ and $g(x)$ and a point $x_0 \in \mathbb{R} \cup \big\{+\infty,-\infty\big\}$ we say that $f(x)\sim g(x)$ as $x\to x_0$ $\iff$ $lim_{x\to x_0} \frac{f(x)}{g(x)}=1$ ...
1
vote
1answer
45 views

Small $\delta$ behavior of rational integral

I need to do the following integral, and extract the leading small $\delta$ behavior: $$I(\delta, A)=\int_0^1 dx \, x^n \frac{1}{(x^2 A+\delta)^\nu},\qquad 0< n < \nu, \enspace ...
1
vote
1answer
17 views

Asymptotic approximation to radial wave function

This seemingly easy analysis is driving me up the wall. $$\frac{\text{d}^{2}u}{\text{d}\rho^{2}}=\left[1-\frac{\rho_{0}}{\rho}+\frac{l(l+1)}{\rho^{2}}\right]u$$ why is it for $$\rho\rightarrow0,$$ ...
3
votes
1answer
66 views

Least positive eigenvalue of the BVP $y''-\lambda y'+\frac{2\lambda-1}{x}y=0$, $y(0) = y(1/2) = 0$

Find the first positive eigenvalue $\lambda$ of the boundary value problem over $x\in [0,\frac{1}{2}]$. $$y''-\lambda y'+\frac{2\lambda-1}{x}y=0, \quad y(0)=y(\tfrac{1}{2})=0.$$ My approach: I ...
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
4answers
115 views

Asymptotic behaviour / non-linear ODE

I'm trying to find the behaviour at large $t$ of solutions to the non-linear differential equation: $$\dfrac{d^2y}{dt^2}-\left(\dfrac{dy}{dt}\right)^2+(2-a)t\dfrac{dy}{dt}+2ay=0$$ I tried to replicate ...
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 ...
0
votes
3answers
100 views

On a manipulation of little oh in $R^n$.

Take $x \in R^n$. and take $ f(x) = o(||x||)$, where $f: R^n \rightarrow R^m$ is a linear function. This means by definition that $$\lim_{x \rightarrow 0} \frac{f(x)}{||x||} = 0 $$ Now we can find ...
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
63 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 ...
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 ...
2
votes
2answers
38 views

Asymptotic behaviour of mean absorption time at the Moran model

In the Moran model, a model from population genetics, the mean time until absorption is given by $$ \tau _i =N \left( \sum_{j=1}^i \frac{N-i}{N-j} + \sum_{j=i+1}^{N-i} \frac{i}{j} \right),$$ where ...
4
votes
3answers
106 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 = ...
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
46 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.
2
votes
0answers
49 views

Solving for a $v$ in $\sum a_i e^{b_i (z^2+d_i) + c_i v}$

I have an equation in complex domain, $$P(e^u,e^v)=\sum_{i=1}^{N} a_i e^{b_i u + c_i v}=0 \;\;\;\text{(A)}$$ and by redefining, at the roots (I'm only showing work for one root), the first ...
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 ...
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 ...
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
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}$. ...
4
votes
1answer
86 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 ...
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 ...
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
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 ...
12
votes
1answer
166 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 ...
6
votes
2answers
89 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
29 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
28 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 ...
1
vote
1answer
40 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: ...
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 ...
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
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 ...
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 ...
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 ...
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
60 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
64 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 ...