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

learn more… | top users | synonyms (1)

0
votes
1answer
47 views

Prove $\log(n) = O(n)$ using induction

I am using the lecture notes here on page 19 (Algorithm Notes 1) example 1 is the inductive proof of $\log(n) = O(n)$. I understand the base case but I don't understand the rest of the example. ...
0
votes
0answers
50 views

Calculating Running Time (in seconds) of algorithms of a given complexity

I've tried to find answers on this but a lot of the questions seem focused on finding out the time complexity in Big O notation, I want to find the actual time. I was wondering how to find the ...
0
votes
0answers
9 views

Operations with stochastic little o

In deriving some results I arrived to this expression: $$ A_n=n*o_p(||\frac{h_n}{\sqrt{n}}||)+o_p(1) $$ where $h_n$ is a random vector of dimension $l \times 1$, $\{h_n\}_n=O_p(1)$, $||\cdot ||$ ...
1
vote
1answer
16 views

Growth rate of two functions

It's obvious that $x^2>2x+1$ for $x\ge 3$ - we just observe that for $x\ge3$, $3^2>2\cdot 3+1$ and the LHS grows much faster than the RHS. But how to determine: how faster does the LHS grow (and ...
2
votes
1answer
47 views

Asymptote to sin x/x?

I have seen elsewhere that: $y=\sin x/ x$ has a horizontal asymptote of $y=0$, as it approaches that line as x tends to +/- infinity. Now, why does it not have an asymptote of $x=0$ or $y=1$, as ...
1
vote
0answers
31 views

Big O Notation Clarification

Working through a textbook on algorithms (CLRS intro to algorithms) and just wanted to see if someone could help me understand one of the exercises at the end of a chapter. Problem: Is $n^{2 + 1} = ...
1
vote
1answer
58 views

Is this number in $O(\log(n))$?

Is this number $\big[\log(n) + \sum_{j=1}^{n-1} (\log(j) - (j+1)(\log(j+1)) + j \log(j) +1)\big] \in O(\log(n))$? I simplified it to $\big[\log(n) + \sum_{j=1}^n (-\log(n+1) - j(\log(n)) + 1)\big]$.
4
votes
2answers
65 views

If an eventual inequality holds for $f$ and $g \sim f$ then does it hold for $g$?

Suppose $f$, $g$, are non-negative functions such that $f \sim g$ (meaning that $f(x)/g(x) \to 1$ as $x \to \infty$). If for all $\lambda > 1$ there exists an $\eta > 0$ such that $$f(\lambda ...
0
votes
0answers
19 views

Operations with stochastic big and little o

I have a question related to stochastic little/big o notation. Consider a sequence of real-valued random variables $\{X_n\}_n$. Is it correct $O_p(1)+X_no_p(1)=O_p(1)$ ? Why? I know that ...
0
votes
0answers
13 views

Definitions Continuity Using the Order (Landau) symbolism.

Is an $o(1)$ function always continuous?
1
vote
0answers
12 views

asymptotic normality of m-estimator

I' struggling with an argument in van der Vaart proof of theorem 5.21 at p.52: ...
3
votes
1answer
25 views

Big Theta with Negative Coefficient Problem

I had a question in regards to solving a Big-Theta problem. Our professor wanted us to prove that $n^3 - 47n^2 + 18 = \Theta(n^3)$ and to do so rigorously, meaning he does not want us to use the below ...
0
votes
1answer
16 views

Combining deterministic and stochastic asymptotics

Consider a sequence of real-valued random variables, $\{X_n\}_{n}$. Suppose that (*) $X_n \rightarrow_p X$. Consider $\lim_{n \rightarrow \infty} P(X_n>0)$. What I have seen doing in ...
0
votes
1answer
9 views

Supremum transformations with stochastic convergence

Consider a sequence of real-valued random variables depending on a parameter $\theta \in \Theta \subseteq \mathbb{R}$, $\{X_n(\theta)\}_{n}$. Suppose that (*) $X_n(\theta)\rightarrow_pX(\theta)$ ...
0
votes
0answers
33 views

The ratio of two asymptotically normal distribution

Let $(X,Y)$ be asymptotically normal with their means, variances, and a covariance. Then, I would like to show $X/Y$ is also asymptotically normal. I think there should be some references related to ...
1
vote
0answers
20 views

Three term inner and outer solution to a boundary layer problem

I am unsure how to proceed with the current equation to determine a three-term outer expansion and three-term inner expansion due to the nature of the equation. Equation: $\epsilon ...
0
votes
2answers
19 views

Is this easy to prove? $\forall N, k \gt 0$, $\pi(x) - \pi(N) \gt \frac{x-N}{2k}$ for all sufficiently large $x$.

Let $\pi(x)$ be the prime counting function. Knowing that $\pi(x) \sim \dfrac{x}{\ln x}$. How could you prove that $\pi(x) - \pi(N) \gt \dfrac{x - N}{2k}$ for all $x \geq $ some $X_0$? I think ...
0
votes
1answer
17 views

Summation of big oh terms

I read about asymptotic notation .I understood the limit definition of big oh notation.But while going about calculating O(1)+O(2)+.......…..+O(n),the sum comes out to be O(n ^2).Can anyone explain ...
0
votes
1answer
27 views

determine two-term outer, inner and uniform expansions

Consider the equation; determine the two-term outer, inner and uniform expansions assuming that $0<\epsilon<<1$ $$\epsilon \frac{d^2y}{dx^2}+\frac{dy}{dx}+y=0, \hspace{5mm} ...
10
votes
2answers
275 views

Proof of $\sum_{n=1}^{\infty} \frac{x^n \log(n!)}{n!} \sim x \log(x) e^x$ as $x \to \infty$

Prove that $$\sum_{n=1}^{\infty} \frac{x^n \log(n!)}{n!} \sim x \log(x) e^x \,\,\,\text{as}\,\,\, x \to \infty$$ and $$\sum_{n=1}^{\infty} \frac{(-x)^n \log(n!)}{n!} \to 0 \,\,\,\text{as}\,\,\, x \to ...
1
vote
2answers
23 views

Delta Method corollary

Consider the Delta Method as stated in van der Vaart Theorem 3.1 at page 26 (you can find the page here ...
0
votes
0answers
60 views

Asymptotics for the probability a discrete Brownian bridge remains below a logarithmic barrier

Let $(\mathcal{Z}(i))_{1\leq{i}\leq{\text{N}}}$ be a discrete Brownian bridge of lifespan $\text{N}$ conditioned to start and end at $0$, i.e. $\mathcal{Z}(1)=0$ and $\mathcal{Z}(\text{N})=0$. I would ...
0
votes
0answers
12 views

Decay of a Fourier Transform with parameter

Given $t>0$, consider the following function $f_t:\mathbb{R}\rightarrow\mathbb{C}$ $$f_t(x)=\begin{cases}e^{-tx-itx^2}&x\geq 0\\ 0&x<0\end{cases}$$ Now, let $\widehat{f_t}$ the Fourier ...
0
votes
1answer
24 views

Definitions On Landau Notation (Big O and little o)

What are the definitions on Big O and little o for when $x \in R^m$ approaches $s\in R^m$ And not $x$ going to infinity?
0
votes
0answers
25 views

Asymptotic expansion using method of steepest descents

I am trying to find the first term in the asymptotic expansion of $$\frac{1}{2\pi i}\int_{c-i\infty}^{c+i\infty}\frac{1}{s^2}e^{t(s-m\sqrt{s^2-1})} ds $$ where $0<m<1$, $c<1$, as $t$ ...
1
vote
1answer
27 views

gamma function with negative argument

For $k=0,1,2...$ and small $z$ I want to show that $$\Gamma (-k + z) = \frac{ a_k}{z} + b_k + O(z).$$ I understand that the gamma function cannot be expressed as $$\Gamma ( z) = \int_0 ^\infty ...
0
votes
1answer
43 views

First order, inner, outer and uniform approximations of boundary layer problem

$\epsilon \frac{d^2y}{dx^2}+2\frac{dy}{dx}+2y=0, y(0) = \alpha, y(1) = \beta$ Since we have the general form: $\epsilon \frac{d^2y}{dx^2}+a(x)\frac{dy}{dx}+b(x)y=0$ we can see that $a(x) = 2 >0$ ...
4
votes
1answer
163 views

Giving tight asymptotic bounds for $T(n)=T(\frac{n}{\log n}) + \log\log n$

I don't like coming here for such matters, but this is a homework problem from my Analysis of algorithms class. I've come along the Akra-Bazzi method and different variations on the matter , read ...
0
votes
1answer
18 views

Convergent, Bounded, O(1) sequences

Consider a sequence of real numbers $\{a_n\}$ and these 3 definitions: (1) $\{a_n\}$ is bounded: $\exists k>0$ s.t. $-k \leq a_n\leq k$ $\forall n \in \mathbb{N}$ (2) $a_n=O(1)$: ...
0
votes
1answer
18 views

Relation involving little-o.

I am trying to show that the following relation holds: \begin{equation} \log(1+ax) = log(x) + o(log(x)) \end{equation} as $x\rightarrow \infty$, where $a$ a positive number. I tried using Taylor ...
0
votes
1answer
26 views

Leading order of behavior of nth derivative of Gamma function evaluated at x=1 as n approaches infinity

I'm working from Bender and Orszag's "Advanced Mathematical Methods for Scientists and Engineers: Asymptotic Methods and Perturbation Theory" and I am trying to solve problem 6.48(b): Find the ...
1
vote
1answer
20 views

Understanding the “vertical shift” property of big Oh

So I have difficulty understanding the big Oh property that says that if $\epsilon$ is some constant and $\epsilon < f$ on a neighborhood of infinity, then $\alpha + f = \mathcal{O}(f) $ . I have ...
0
votes
0answers
37 views

An aquidistributed sequence

Prove that $\{an^\sigma\}$ is equidistributed in $ [0,1) $,if $\sigma>0$ is noninteger and $a\neq 0$. I know how to solve this problem if $\sigma <1$ , so it is not a duplicate of ...
0
votes
1answer
25 views

is $O(3^k)$ polynomial for $k\in o(n)$?

For variable $n\in \mathbb{N}$, $O(3^n)$ is certainly an exponential, fix any integer $k\in o(n)$, is the function $O(3^k)$ polynomial ? If not when is it possible for $O(3^k)$ to become polynomial ...
1
vote
1answer
82 views

Solving limits without l'Hopital

I've encountered several limits that need to be solved in order to calculate the coefficients in asymptotic formulas for elementary functions, e.g.: $$ \lim_{x \to 0}\frac{\sin x -x}{x^3} $$ $$ ...
3
votes
3answers
55 views

Asymptotic Equivalence $e^{x^2+x} \sim e^{x^2}$?

I've a doubt regarding the asymptotic equivalence of two functions. From the definition $f(x)\sim_{x\to x_0} g(x) \iff \lim_{x\to x_0} \frac{f(x)}{g(x)} =1$ While I was trying to determine the ...
2
votes
2answers
48 views

Exact solution of Second order ODE

We have the second order differential equation $\epsilon \dfrac{d^{2}y}{dx^{2}} + \dfrac{dy}{dx} +y = 0$ with boundary values $y(0)=0,\, \, \, y(1)=1$. I would like to get the exact solution in ...
2
votes
1answer
102 views

In the limit of $N \rightarrow \infty$, find solution $z$ to $\text{e}^{-(z+N)} \sum \limits_{k=0}^{N} \frac{(z+N)^k}{k!}=\frac{1}{2}$

Fix an integer $N$, and consider the unique positive solution $z$ to the following equation: $$\text{e}^{-(z+N)} \sum \limits_{k=0}^{N} \frac{(z+N)^k}{k!}=\frac{1}{2}$$ For $N = 0$, we find that $z ...
0
votes
0answers
17 views

Relation between existence of moments and Big O notation

Consider a sequence of real-valued random variables $\{X\}_{n \in \mathbb{N}}$. Could you help me to clarify the relation (if any) between the following two assumptions: 1) $|E(X_n^p)|<\infty$ for ...
0
votes
1answer
34 views

Relation limsup, liminf, lim

Consider a sequence of real numbers $\{X_n\}_{n \in \mathbb{N}}$ and suppose that I have shown that $\forall \epsilon>0$, $\limsup_{n\rightarrow \infty} X_n-X\leq\epsilon$ and ...
1
vote
3answers
49 views

“Good approximation” for the inverse function of $y = x\log_2 x, \hspace{2mm}x>1 $?

I encountered to solve $x$ from $y$ in the equation $y = x\log_2 x ,\hspace{2mm} x>1$, which is known to have no closed form for its inverse function ...
3
votes
0answers
46 views

Which version of Taylor Theorem is this?

Suppose $X$ is a random variable and $\psi(t)=E[\exp(itX)]$ is its characteristic function. Let $K(t)$ be the principal value of the logarithm of $\psi(t)$. Suppose further that ...
2
votes
1answer
68 views

What is happening in this integration?

I found in Peskin-Schroeder, while reading Quantum Field Theory. the following integration. $$\frac{1}{4\pi^2 r}\int_m^\infty \frac{se^{-sr}}{\sqrt{s^2-m^2}} = e^{-mr}$$ at the limit $r \rightarrow ...
2
votes
1answer
159 views

Asymptotic value of permutations of general Rubik Cube

I found this on C|NET, and wondering if there was anything like a $1000\times1000\times1000$ cube? And how many arrangements would it have? Or if this is too much, how about an asymptotic formula for ...
2
votes
0answers
41 views

Bounds on twin prime counting function

I read somewhere (unfortunately I cannot find the paper again) that the twin prime counting function $\pi_2(x)$ satisfies $\pi_2(x) \leq C\frac{x}{\log^2x}$ for some constant $C$. How would one prove ...
2
votes
1answer
58 views

Find location and width of boundary layer

Consider the boundary value problem $$\varepsilon (2y+y'')+2xy'-4x^2=0$$ subject to $y(-1)=2$ and $y(2)=7$, for $-1 \leq x \leq 2$, $\varepsilon \ll 1$. Find the location and width of the boundary ...
2
votes
1answer
26 views

Big O: Trouble finding Witnesses

I am trying to follow this example but I am stumped by where numbers are coming from: Show that $f (x) = x^2 + 2x + 1 $ is $O(x^2). $ The solution is as follows: We observe that we can readily ...
4
votes
1answer
70 views

Decreasing by $\sqrt{n}$ every time

We start with a number $n>1$. Every time, when we have a number $t$ left, we replace it by $t-\sqrt{t}$. How many times (asymptotically, in terms of $n$) do we need to do this until our number gets ...
1
vote
3answers
79 views

Limit as $n$ goes to infinity of $n^22^n/n!$ [closed]

I have read in a book that $( n^2 2^n)$ is superior to n! this means that the limit below will at least be a constant and $n! = O( n^2 2^n )$, but l could not manage to find it, any ideas ...
3
votes
1answer
59 views

Evaluation or asymptotic for $\int_1^x y\sin\left(\frac{2\pi (y-1) x}{y}\right)dy$

Truly, my genuine problem (see Appendix for context) is compute in a closed form or an asymptotic, for real $x\geq 1$, for $$\int_1^x\left(\int_0^{y-1}\cos\left(\frac{2\pi t ...