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

Prove that (x+1)! is not O(x!)

Discrete math question which is as follows: Prove that (x+1)! is not O(x!) using only the definition of Big-Oh notation. (Hint!: log(a * b) = (log a + log b)) I used a proof by contradiction saying ...
2
votes
0answers
167 views

Big-O Notation for remainder terms in Taylor expansion

The Big-O notation is commonly used in Taylor expansions of the form $$f(x+\epsilon)=f(x)+\epsilon f'(x)+O(\epsilon^2)$$ to say that the remainder term grows at least quadratic around $\epsilon=0$. ...
2
votes
0answers
337 views

Free lecture notes to Carl Bender's Mathematical Physics video lecture course?

I am just watching Carl Bender's Mathematical Physics video lecture course (about asymptotics and its application in physics) http://www.perimeterscholars.org/328.html which is great! Are there any ...
2
votes
0answers
76 views

How to maximize speed of rest position approach of nonlinearly damped spring oscillator?

Inspired by comments to answer for this question: Suppose we have a system which is described by the equation $$\ddot x=-x+g(\dot x),$$ with initial conditions $x(0)=1$, $\dot x(0)=0$. If ...
2
votes
0answers
38 views

Asymptotic behaviour of oscillating integral

I'm interested in the big $x$ ($x \to \infty$) behaviour for the following integral $\int_{-\infty}^{\infty} \frac{dk}{\sqrt{k^2+1}} \frac{e^{-\sqrt{k^2+1}/2}}{1-e^{-\sqrt{k^2+1}}} e^{ikx}$ After a ...
2
votes
0answers
281 views

First disagreement in PROUHET THUE MORSE exponentially big?

Let two sequences of integers be $a_1, \cdots, a_n$ and $b_1, \cdots, b_n$ such that with $a_i \in \{1, \cdots n\}$ and $b_i \in \{1, \cdots, n\}$. Let $k$ be the min integer such that $\sum_{i=1}^n ...
2
votes
0answers
59 views

find the the variable that maximizes a function

I have a function that I am trying to find for what input it maximizes. $$ f(n) = {\binom{S}{2}}^{n/S}$$ I need to find the $S$ for which this function maximizes (for infinite $n$). more generally, ...
2
votes
0answers
55 views

Asymptotics for exponential integrals

Suppose I have a situation where I want to find an asymptotic expansion as $x \to \infty$ for an integral of the form: $$ \int_{a}^{b} f(t) e^{-\phi(t) x} \mathrm{d}t$$ Let us also suppose that ...
2
votes
0answers
36 views

Asymptoticity of a definite integral

friends! I read on a book that, for $\alpha>1$, "being $g$ continuous in 0 [really $g$ is continuous in $[0,1]$, if it were useful to know] and approaching the extremes of the integral 0 for $n\to ...
2
votes
0answers
37 views

Farey Sequences and how evenly is the sequence distributed

Given any $\alpha,\beta\in (0, 1)$, $k\in Z^+, n > 1$ is this true ($\mathcal{F}_n$ denotes the $n$th Farey sequence, and $\mathcal{F_n}^{\prime} = \{q:q = a + b, a\in\mathbb{Z}, ...
2
votes
0answers
33 views

A question regarding binomial coefficient

This question arose during solving an information theory problem. Suppose $l$ is the smallest integer such that $$2^l\geq {n\choose k}$$ define $\rho=\frac{k}{n}$. How we can characterize $\rho$ as a ...
2
votes
0answers
44 views

The characterization of asymptotic dimension

Let X be a metric space. The following conditions are equivalent (a)asdimX = n (b)n is the smallest integer such that for every R > 0 there exists n + 1 families Ui i=0,1,2,...,n, and S > 0 such ...
2
votes
0answers
177 views

representing integers as linear combination of integers

Let $a,b,a',b'$ be $r-\epsilon_1$ bit positive integers. Let $c,d$ be $s+\epsilon_2$ bit positive integers. Fix a pair $c,d$ and vary $a,b$ over all $r-\epsilon_1$ bit numbers. Do we have almost ...
2
votes
0answers
31 views

Is there a 2D 3-colorstate mobile automaton that grows like $ln^{0,5}(t)$?

Define an integer function $f(t)$ for an integer $t>25$ such that $|f(f(t)) - ln(t)| < \sqrt {ln(t)}+2$. Define $L(X(t))$ as the number of nonwhite states at iteration $t$ of mobile automaton ...
2
votes
0answers
86 views

Asymptotic of Stirlings numbers of the first kind

I am trying to find some asymptotic expression for the unsigned stirling numbers of the first kind. Lets denote them by $|s(n,k)|$, and suppose that $k$ is fixed. So far I have tried using the fact ...
2
votes
0answers
80 views

Upper Bound on $\frac{1}{1-\beta u}-\sum\limits_{n=0}^{\infty}\frac{e^{-u}u^n}{n!(1-\beta(n+1))}$

Is there any procedure to find an upper bound of the following expression? $$\frac{1}{1-\beta u}-\sum_{n=0}^{\infty}\frac{e^{-u}u^n}{n!(1-\beta(n+1))}$$ Here $u,\beta\in\mathbb{R},\ u>1,\ ...
2
votes
0answers
150 views

Convergence to non-degenerate limit.

If $X_1,X_2......$ follow Poisson$(λ)$. Can we find suitable constants $a_n$ and $b_n$ such that $a_n(Y_n - b_n)$ converges to a non degenerate limit where $Y_n = (1 - \frac{1}{n})^{n\bar{X}_n}$. I ...
2
votes
0answers
55 views

Bounds on a rapidly increasing sequence

I read about a sequence similar to this one here on Stack Exchange a while back, somebody used it as an example for something that I can't recall! However, when I read about it it made me come up with ...
2
votes
0answers
103 views

Aymptotic analysis for Following fucntions

Below is an excercise from algorithm design manual For each pair of expressions (A,B) below, indicate whether A is O, o, Ω, ω, or Θ of B. Note that zero, one or more of these relations may hold for a ...
2
votes
0answers
58 views

Asymptotics and Related Properties

I have a rather general question: If there are two integer sequences such that $$\lim_{n\to\infty}A(n)/n=\lim_{n\to\infty}B(n)/n=c$$ is there anything else that can be said about them necessarily? ...
2
votes
0answers
51 views

Solving $B(n)=3B(\frac{n}{\log_{2}n}) +n$ using master theorem.

First of all sorry if this has been posted before, I found lots of master theorem questions on the search but not one like this. I am familiar with master theorem but a little uncomfortable with ...
2
votes
0answers
106 views

Weighted sum of ratio of partial sum of binomial coefficients

I would like to approximate the following sum when $n \rightarrow \infty$ and $n \gg k$, $$\sum_{x = k}^n \sum_{y > x}^n \frac{\sum_{m = 0}^{k - 1} {y - 2 \choose m}}{\sum_{m = 0}^k {y - 1 \choose ...
2
votes
0answers
65 views

Bounding an implicitly defined sequence

I have a sequence $\lambda_0,\lambda_1,\ldots,$ which is defined implicitly as $$ \lambda_0 = \frac{1}{2},$$ and $$\lambda_{k+1} = \max_{\lambda\in[1,b]} \left\{\frac{1}{2\lambda}\prod_{0\leq ...
2
votes
0answers
45 views

How prove this $\frac{|x-z|}{|x-y|}=1+\frac{1}{|x|}\hat{x}\cdot(y-z)+O(1/|x|^2)$

prove that $$\dfrac{|x-z|}{|x-y|}=1+\dfrac{1}{|x|}\hat{x}\cdot(y-z)+O(1/|x|^2)$$ for $|x|\longrightarrow \infty$ where $$\hat{x}=\dfrac{x}{|x|}$$ This problem from book,following is my idea: ...
2
votes
0answers
111 views

At large times, $\sin(\omega t)$ tends to zero?

While doing a calculation in quantum mechanics, I got a expression $\sin(\omega t)$, and my prof said if I consider the consider at large times, then i can assume that this goes to zero because at ...
2
votes
0answers
138 views

Upper bound for linear function

What may be more surprising is that when $a>0$, any linear function $an +b$ is $\mathcal{O}(n^2)$ which is easily verified by taking $c = a + |b|$ and $n_o = \max (\frac{-b}{a}, 1)$. $$an + b ...
2
votes
0answers
139 views

Big and Small O Notation

I am currently trying to learn the meaning of the Landau Symbols a bit better by solving exercices, namely the following three: $f_1(x) + f_2(x) = O(g_1(x) + g_2(x))$ given that for each f(x) the ...
2
votes
0answers
86 views

Series expansion of a series

I would like to perform an asymptotic expansion of the function $$f(x) = \sum_{n=1}^{\infty}\frac{1}{(nx)^2}K_2(n x),$$ where $K_2(x)$ is the modified Bessel function of the second kind, around $x=0$. ...
2
votes
0answers
76 views

asymptotics of $ J_{iu} (ia)$ for a Bessel function

Let $J_{iu}(ia)$ be the Bessel function of imaginary order. ($a$ is a real number (positive or negative) and $u$ is also real.) In the limit $u \to \infty $ how does the function $J_{iu} (ia)$ ...
2
votes
0answers
120 views

Are my calculations concerning the growth rate of $f(n) = \sum_{k=0}^n \min(2^k, 2^{2^{n-k}})$ correct?

Having $$f(n) = \sum_{k=0}^n g_n(k), \; g_n(x) = \min(2^x, 2^{2^{n-x}})$$ I want to know whether $\mathcal O(f(n)) \subsetneq \mathcal O(2^n)$. Since $g_n(x) \le 2^x$ it is at least $f(n) \in \mathcal ...
2
votes
0answers
51 views

Is this kind of approximation correct?

I was trying approximate the variance of a ratio of two random variables. I used to approximate it through Taylor's expansion: Assume $\sqrt{n}\big(X-E(X)\big)=O_p(1)$, ...
2
votes
0answers
75 views

Bound the probability of unlikely escape through one end of a thin rectangle

Consider the following elliptic PDE boundary value problem, \begin{eqnarray} & a u_x + b u_y + \frac{\alpha}{2} u_{xx} + \beta u_{xy} + \frac{\gamma}{2} u_{yy} = 0 \;, \quad {\rm ~for~} ...
2
votes
0answers
91 views

Growth of number of distinct elements

Let $A_k$ be a random variable which represents the number of distinct integers seen after sampling $k$ independently and uniformly at random from the range $1, \dots, n$. Let $B_k$ be a random ...
2
votes
0answers
106 views

Asymptotic expansion of $x_{n}$, $x_{n}=\frac{1}{\tan(x_{n})}$

I would like to find a two-term or a three-term asymptotic expansion of $x_{n}$ the unique solution of $$x_{n}=\frac{1}{\tan(x_{n})}$$ on the interval $]n\pi,n\pi+\pi[ $ We have: $$ ...
2
votes
0answers
61 views

gamma funtion and estimates-typo or mistake?

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 ...
2
votes
0answers
70 views

On bounding the average cost of top-down merge sort

Let $A_n$ be the average number of comparisons to sort $n$ keys by merging them in a top-down fashion (see any algorithm textbook). It can he shown that $$ A_0 = A_1 = 0;\quad A_n = ...
2
votes
0answers
49 views

Local polynomial fitting using Taylor expansion

My question is about the usage of Taylor expansions when dealing with asymptotics in local polynomial fitting. The expressions that set me of are of the type: $$ g(X_i) = \sum_{j=0}^{p} ...
2
votes
0answers
208 views

Asymptotic bounds for a sum

I have this sum, which probably doesn't exist in closed form. $$\displaystyle ...
1
vote
0answers
11 views

Big-O Notation exponentials

I'm learning about Big-O notation for algorithm runtime, and I need some help understanding one part. I read that for the constant, c, does not matter as the function increases rapidly. Does that ...
1
vote
0answers
26 views

What does $\mathbb P(\overline{\mathbf X} = \mathbf x)$ mean

I am reading Peter Hall's "the bootstrap and edgeworth expansion". In Theorem 2.3 on page 57, it claims that if the characteristic function $\chi$ of a $d$-dimension random variable $\mathbf X$ ...
1
vote
0answers
32 views

A combinatorial way to understand $\sum \log^2 n $

Stirling's formula has many derivations using the factorial function: $$ \log N! = \sum_{n=1}^N \log n = \sum_{n=1}^N \sum_{m=1}^n \bigg( \log m - \log (m-1) \bigg) = \sum_{n=1}^N \sum_{m=1}^n - ...
1
vote
0answers
20 views

Show that $f(b^i n) \le c^i f(n)$

Let $f$ be a b-smooth function. Let $c$ and $n_0$ be constants such that $f(b n) \le c f(n)$ $\forall $ $n \ge n_0$. Show that $\forall $ $ i \in \mathbb{N}, f(b^i n) \le c^i f(n)$ I thought I should ...
1
vote
0answers
31 views

Asymptotic Formula for Sum

I am trying to find an asymptotic formula for the sum of the following: $\sum _{x=1}^{\infty } x \left(\left(1-\frac{\Gamma (x,\lambda )}{\Gamma (x)}\right)^n-\left(1-\frac{\Gamma (x+1,\lambda ...
1
vote
0answers
72 views

Asymptotic distribution and stability?

I am working with asymptotic theory and I have some things I am unsure about. For example if one uses the Central Limit Theorem as an example: $\sqrt{n}\bigg(\bigg(\frac{1}{n}\sum_{i=1}^n ...
1
vote
0answers
38 views

Asymptotic Proof

Can someone explain this asymptotic proof to me.I am stuck at the inductive step and get lost around this step $2 × n! < (n + 1) × n!$ $$2n = o(n!)$$ True Proof: In order to $2n = o(n!)$ be true, ...
1
vote
0answers
32 views

Summation involving digamma and floor functions

I am trying to find an asymptotic expansion for the following sum: $$\sum_{n=1}^K \frac{\phi_0( 1/2+n+\lfloor(2n-1)/\sqrt{2}\rfloor)}{(4n-2)}$$ where $\phi_0$ is the digamma function and $\lfloor ...
1
vote
0answers
29 views

How would you prove this Big Omega complexity?

We're given $f(n)=\frac{1}{5}n^2-30n-5$ and $g(n)=n^2$, and are asked to prove $f \in \Omega(g)$. The exercise was posted, but no solution is given (this is not an assignment question). So by ...
1
vote
0answers
19 views

Asymptotic expansion of integrals of the form $\int_{\mathcal{D}} \exp(\lambda\, \phi(x))\, g(x) \,dx$ for small $\lambda.$

In the limit $\lambda\to\infty$ the asymptotic expansion of integrals of the form $\int_{\mathcal{D}}\exp(\lambda\,\phi(x))\,g(x)\,dx$ (where $\mathcal{D}\subseteq \mathbb{R^n}$ denotes the domain of ...
1
vote
0answers
46 views

Proving $n^{10\log(n)} = O((\log^n(n))$

I need to decide which of the following is correct: $n^{10\log(n)} = O((\log^n(n))$ $n^{10\log(n)} = \Theta((\log^n(n))$ $n^{10\log(n)} = \Omega((\log^n(n))$ So I'm saying $n^{10\log(n)} = ...
1
vote
0answers
24 views

Asymptotic expansion of a Laplace-type integral with a “manifold of maxima”

Consider the integral $$ I(\alpha)=\int_0^1 dx_1 \int_0^1 dy_1\int_{x_1}^1dx_2\int_{y_1}^1dy_2\,e^{-\alpha(x_2-x_1)(y_2-y_1)} $$ in the limit $\alpha\rightarrow\infty$. To find the asymptotic ...