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
0answers
31 views

Product of complex numbers $m+in$ with $0 < m,n \leq N$

I am trying to look for a generalization of Stirling's formula to complex numbers. In the integer case: $$ \log n! = \sum_{k = 1}^n \log k \approx \int_1^n \log x \, dx = n \log n - n$$ For the ...
-2
votes
1answer
34 views

What does θ(1) means in this equation?

Hello I am trying to understand this recurrence equation with no success. $ T(n) = T(n / 2) + θ(1)$ Base case : $T(1) = θ(1)$ and the solution is $θ(log_2 n)$. ...
1
vote
1answer
20 views

Is this true: $\frac{f(x)}{1-c-o(1)}= \frac{f(x)}{1-c}(1-o(1))$

Let $f$ be a function, for example $f(x)=log(1+x)$ and let $c$ be some constant $>0$ (for simplicity, we may assume that it is different from 1). Is this true: $$\frac{f(x)}{1-c-o(1)}= ...
1
vote
1answer
253 views

asymptotic behavior of the real part of the Riemann zeta function for $0<\sigma<1$

consider the zeta function $\zeta(\sigma+it)$ for $\sigma>1$ : $$\zeta(\sigma+it)=\sum_{n=1}^{\infty}\frac{1}{n^{\sigma+it}}$$ And: $$\zeta(\sigma-it)=\sum_{n=1}^{\infty}\frac{1}{n^{\sigma-it}}$$ ...
0
votes
3answers
68 views

Is there a simpler proof that $n^2 = O(2^n)$?

I am wondering if there is a simpler proof that $n^2 = O(2^n)$ which doesn't involve several layers of induction. My proof is as follows (sorry for the bad formatting). Proof: $n^2 = O(2^n)$ We will ...
1
vote
2answers
51 views

Behavior of transient states as $n \rightarrow \infty$

Let $(X_n)_{n \geq 0}$ be a discrete time-homogeneous Markov chain on the state space $E$. Suppose $T \subseteq E$ is the set of transient states. Can it be that we stay forever in $T$, with ...
0
votes
0answers
21 views

Compute asymptotic expansion of an integral along the unit circle

I want to compute the asymptotic expansion of the following integral with $t\rightarrow +\infty$ $\int_C\dfrac{(1+u)^{t+4}}{u^5}du$ where $C$ is the unit circle. I really appreciate your help. By ...
0
votes
2answers
27 views

Need help figuring out substitution with recurrence equation. [duplicate]

I need help with an Algorithm text book problem. The problem is the following T(n) = 2T(n/2) + n We guess that the solution is T (n) = O(n lg n). Our method is to prove that T (n) ≤ cn lg n for an ...
1
vote
0answers
91 views

The Big-$\mathcal{O}$ notation

Suppose that you take out a $\$15,000$ loan to purchase a car. The loan has an interest rate of $3\%$ per year, compounded monthly. The formula for the amount of interest accrued over a time period ...
-1
votes
2answers
47 views

Prove $\frac{1}{(1+z)^2}=1-2z + \mathcal{O}(z^2)$ as $z \to 0$ [closed]

Prove: $$\frac{1}{(1+z)^2}=1-2z+\mathcal{O}(z^2)$$ as $z\to 0$.
2
votes
0answers
42 views

Asymptotic conditional distribution of $\bar{Y}\mid\bar{X}=x$

I'm reviewing for my qualifying exam and I'm stuck on part of a problem. Setup Suppose that $(X,Y)$ are two random variables with joint distribution $ \begin{equation} ...
1
vote
1answer
16 views

Comparing Serveral Asymptotic Analysis Question

I have the following: $n^2\log(n)$, $2^n$, $2^{2^n}$, $n^{\log(n)}$, $n^2$. In increasing order, I think their order of growth is $n^{\log(n)}$ < $n^2$ < $n^2\log(n)$ < $2^n$ < $2^{2^n}$ ...
2
votes
3answers
83 views

$o(x)$ and $O(x^2)$

How to prove, that $O(x^2) \subset o(x) $ when $x \to 0$? How should i use the definitions of Big O : $ \exists C>0, \exists \delta : |x|<\delta, |f(x)| \leq C|x^2| $ and little o: $\forall ...
3
votes
1answer
95 views

Non linear second order ODE

I really need help solving this : $$y_{xx}-\left(y^{3}-y\right)-\varepsilon\frac{1}{2}\left(1-y^{2}\right)=0 $$ With boundary conditions : $$ y(\pm \infty )=-1 $$ I need to find a solution that ...
2
votes
2answers
33 views

Why does 0/0 mean there it a hole and not an asymptote?

https://www.khanacademy.org/math/algebra2/rational-expressions/rational-function-graphing/v/finding-asymptotes-example At around 8 minutes he says that we want a number which makes only the ...
3
votes
0answers
50 views

Asymptotic Expansion Method for Pricing American Option

In this Article I faced with Asymptotic Expansion method for pricing American option. the price $P(S,t)$ of this option satisfies the partial differential equation (PDE): $${{P}_{t}}+(r-\delta ...
1
vote
1answer
32 views

How to get value of this binomial coefficient expression?

I am trying to work out an upper bound (big O) of an algorithm I thought of in graph theory field. Basically I have a graph $G=(V,E)$. And a subset of vertices $A=\{a_1,a_2,...,a_k\} ∈ V$ such that ...
3
votes
1answer
40 views

Asymptotics in differential equations

While learning about Bessel functions I've came up with the following argument: Since the Bessel equation is $$y''+\frac{1}{x} y'+ \left(1-\frac{\alpha^2}{x^2} \right) y=0, $$ one might expect ...
1
vote
1answer
43 views

Why is this true: $1- (1-1/n)^{\varepsilon n} \leq \varepsilon + \mathcal{O}(\varepsilon^2)$

In my lecture notes, the following is written: $$1- (1-1/n)^{\varepsilon n} \leq \varepsilon + \mathcal{O}(\varepsilon^2)$$ as $\varepsilon \rightarrow 0$ and $n$ some fixed constant (non-negative ...
0
votes
0answers
29 views

Continuous mapping theorem with density convergence

Let us consider a bivariate random variable $X\in \mathbb{R}^2$ with $pdf$ $f$. Also let, based on a sample of size $n$, let the the estimator of the density be $f_n(x)$ at $x\in \mathbb{R^2}$ and we ...
-1
votes
1answer
111 views

The asymptotic of the first Chebyshev function, using the Prime Number Theorem [closed]

Using the prime number theorem, show that: $\vartheta (x) \sim x$ Where $\vartheta (x) := \sum_{p \le x} \log p$ Any help on this would be great, thanks in advance.
3
votes
1answer
27 views

Is there a way to estimate the number of positive integers less than or equal to $n$ that have a given prime $p$ as a least prime factor

The probability that an integer $p$ divides an integer $x$ is $\dfrac{1}{p}$. From this article on almost prime numbers, the number $\pi_k(n)$ of positive integers less than or equal to $n$ with at ...
0
votes
1answer
76 views

How can I solve this recurrence problem?

Given a function $$ f(n) = f(5n/13) + f(12n/13) + n \;\;\;\;∀n \geq 0 $$ I would like to find a function $g(n)$ such that $f ∈ Ө(g(n))$.
2
votes
1answer
17 views

Show that $\log^{i} n \in O(n^{j})$ for $i,j > 0 $

I want to show that $$\log^{i} n \in O(n^{j})$$ I tried to apply L'Hospital and came up with the following: $$\lim\limits_{n \rightarrow \infty}{\frac{\log^{i} n}{n^{j}}} =$$ $$\lim\limits_{n ...
1
vote
1answer
48 views

What are conditions under which convergence in quadratic mean implies convergence in almost sure sense?

What are the conditions on the sequence on $\{X_n\}$ (apart from the degenerate random variable), under which it can be claim that $||X_n-X||_{L^2(\mathbb{R})}\rightarrow 0$ implies $X_n\rightarrow ...
0
votes
1answer
20 views

Asymptotic behaviour of Hilbert transform

Let $f$ be a bounded function on $\mathbb{R}$ with compact support include in $[-K,K]$. Show that $$ H(f)(x)=\frac{a}{\pi x}+O(\frac{1}{x^2})$$ where $a=\int f(t)dt$ and $H$ denote the Hilbert ...
4
votes
2answers
168 views

Show that if $\int_0^x f(y)dy \sim Ax^\alpha$ then $f(x)\sim \alpha Ax^{\alpha -1}$

Let $f$ be a real, continuous function defined on $[0,\infty)$ such that $xf(x)$ is increasing for all sufficiently large values of $x$. Show that if $$\int_0^x f(y)\,dy \sim Ax^\alpha \quad ...
0
votes
0answers
17 views

Estimating the derivative of the difference function from that of a function

Suppose that $f$ is a twice differentiable function in an interval $(N,2N)$. We write $f_1(n,h)=f(n+h)-f(n)$, i.e., $f_1$ is the difference function. Then, a proof I'm reading estimates that if ...
2
votes
0answers
31 views

An advection problem with weak diffusion in asymptotic analysis.

Consider the following advection problem with weak diffusion: $$ \varepsilon\partial_{x}^2 u=\partial_{t}u+\partial_{x}u, $$ for $−\infty < x < \infty$, and $t > 0$ where $u(x, 0) = ...
0
votes
2answers
19 views

exponential boundedness of components given exponential boundedness of the norm

Let $v:[0,\infty)\rightarrow \mathbb{R}^n$ be a function such that $\forall t\ge 0$, $v_i(t)\ge 0$ and $$ ||v(t)||\le \beta ||v(0)||e^{-at}, t\ge 0$$ with $\beta,a>0$ can I conclude that for all ...
1
vote
3answers
30 views

Is this proof for big-Oh of $(x+2)log(x^9 + 5)$ correct?

Is my proof that $(x+2)log_{2}(x^9+5)$ is $\mathcal{O}(xlog_{2}x)$ correct when x tends towards infinity? $\left | f(x) \right | = \left | (x+2)log_{2}(x^9 + 5) \right |$ $\leq \left ...
3
votes
1answer
71 views

Asymptotic behaviour of $\int_0^1 g(x)\exp(-nx)dx$ as $n\rightarrow\infty$

Let $g:(0,1]\rightarrow\mathbb{R}_+$ be an invertible monotonically non-increasing function that integrates to $1$ and has $g(1)=0$, $g(0)=\infty$; eg. $g(x)=x^{-1/2}-1$ or $g(x)=\ln(1/x)$. I believe ...
2
votes
1answer
48 views

Big-O vs. Best Big-O

Is there a difference between the method to find a big-O function and the method to find the best big-O function. Take for example the following function: $f(n) = 1 + 2 + 3 + ... + n$ It is easy to ...
3
votes
1answer
76 views

Steepest descent method with movable maximum

Suppose we want to find the asymptotic behavior as $n \rightarrow \infty$ of the integral $$\int_C \frac{dz}{z} \frac{e^z}{z^n}=\int_C \frac{dz}{z} \exp(z-n \ln z)$$ where $C$ is some contour in the ...
0
votes
1answer
23 views

Why is this true - easy question concerning asymptotics of exponential

Suppose $\lambda > 0$ is constant as $t \searrow 0$. In my lecture notes it is written that $\left(1+\sum_{k=1}^{\infty} \frac{(-\lambda t)^k}{k!}\right) \lambda t = \lambda t + o(t)$ and ...
1
vote
2answers
61 views

Find whether $f(n) = o(g(n))$ or $g(n) = o(f(n))$

Find whether $f(x) = O(g(n))$ or $g(n) = O(f(x))$ where $$ f(n) = (\log n)^{\log n} \quad\quad\text{and}\quad\quad g(n) = 2^{(\log_2n)^2} $$ I found that $f(n) = n^{ \log {\log n}}$, ...
1
vote
0answers
22 views

Second order perturbed equation

I've been studying asymptotic behavior on Ordinary Differential Equations. While doing some excercises I found out one excercise which has had me thinking for a while, so I am asking humbly for your ...
3
votes
1answer
67 views

Reference for asymptotics on sum

Quite simply I'm looking for the large $m$ asymptotic behavior of \begin{equation} \sum_{k=1}^{m}{m\choose k}\frac{a^k}{k} \end{equation} where $a$ is a constant. This looks easy for someone who knows ...
0
votes
2answers
79 views

Summing divergent asymptotic series [closed]

I found the sine integral si to be $$Si (x)\sim \frac \pi 2+\sum _{n=1}^\infty (-1)^n \left(\frac{(2 n-1)! \sin (x)}{x^{2 n}}+\frac{(2 n-2)! \cos (x)}{x^{2 n-1}}\right)$$ Say I want to find ...
0
votes
1answer
21 views

Estimating size of partial euler product

What estimates are there for product over primes $p \leq x$ $\prod_{p \leq x}(1-\frac{1}{p^{r}})$ given $r$ is positive integer. Something better than $\prod_{p \leq x}(1-\frac{1}{p^{r}}) \leq ...
5
votes
1answer
645 views

Order of growth of the entire function $\sin(\sqrt{z})/\sqrt{z}$

Show that $$f(z)=\frac{\sin\sqrt z}{\sqrt z}$$ is an entire function of finite order $\rho$ and determine $\rho$. I observed that the two determinations of the square root differ only for the signum. ...
0
votes
1answer
21 views

Calculate the asymptotic growth of a sum that contains log or binom

I'm looking for a basic explanation how to calculate the asymptotic growth of sums. Take for example this one: $\sum_{i=1}^{lg(n!)} 2^{n^2}$ or this one: $\sum_{i=0}^{n} {n\choose{i}}$ The ...
1
vote
1answer
54 views

Is $\sqrt{2/(27\pi n)}\sim n^{-1/2}$?

Is $\sqrt{2/(27\pi n)}\sim n^{-1/2}$? Since $$ \sqrt{\frac{2}{27\pi n}}=\sqrt{\frac{2}{27\pi}}\cdot\frac{1}{\sqrt{n}}\sim\frac{1}{\sqrt{n}}=n^{-1/2}, $$ I would say, yes, of course.
1
vote
1answer
31 views

Prove/disprove the following asymptotic bound

Indicating with $p$ and $q$ prime numbers, is it true that for $x\rightarrow\infty$ $$ \sum_{\substack{p\leq x \\ p\equiv 1 ...
2
votes
1answer
27 views

Convergence to a distribution implies convergence of a logarithm?

Let $X_n$ be a sequence of almost surely positive real-valued random variables s.t. $$\sqrt{n} \, \left( X_n -a \right) \to_D \mathcal{N} ( 0, 1)$$ where $\to_D$ denotes convergence in distribution ...
1
vote
0answers
14 views

Stationary Phase method with Singular test function

Consider the following integral $I(x,t) = \int_{-\infty}^{\infty}\{F(k)exp(it\psi(k)) \}dk$ with $\psi(k) = (k-k_0)(\frac{x}{t}) - (\beta(k)-\beta_0)$ where $\beta_0=\beta(k_0)$ and $F(k)= ...
7
votes
0answers
109 views

Heat equation asymptotic behaviour 2

Let $D$ be the domain defined as $D := \{ (x,t): t \in [0,1) , \; x < (1-t)^\alpha \}$. Let $u(x,t)$ satisfy the heat equation $u_t = \frac{1}{2}u_{xx}$ in $D$, with initial condition: ...
0
votes
1answer
37 views

Asymptotic value of a Cauchy Singular integral

Let, $\zeta(x,t) = A_0sin(k_0x)cos(\omega t) + \frac{2k_0A_0}{\pi} \{\int_{0}^{\infty}\frac{cos(kx)cos(\beta t)-cos(k_0x)cos(\omega t)}{k^2-k_0^2}dk\}$ Here $\beta ^2 = gktanh(kh)\ and\ \omega^2 = ...
1
vote
1answer
56 views

Estimation of a probability of marginal values of a random variable

My question is related with this question on combinatorics of 0-1-matrices from MO. Trying to obtain a (asymptotic) lower bound for $\alpha(n)$ by probabilistic approach (see, for instance, “The ...
1
vote
0answers
21 views

Stationary Phase method with Singular test function

I'm stuck at the following integral $I(x,t) = \int_{-\infty}^{\infty}\{F(k)exp(it\psi(k)) \}dk$ with $\psi(k) = (k-k_0)(\frac{x}{t}) - (\beta(k)-\beta_0)$ where $\beta_0=\beta(k_0)$ and $F(k)= ...