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

Showing uniform convergence in probability

Suppose you want to show $sup_{x\in D}|f_n(x)|\to_p 0$, for $n\to \infty$, where $D\subset \mathbb R$ is a compact interval, $f$ is continuous depending on one or more random variables, and $\to_p$ ...
4
votes
4answers
921 views

How do I prove that $2^n=O(n!)$?

How do I prove that $2^n=O(n!)$? Is this a valid argument? ...
3
votes
2answers
159 views

Prove or disprove: $\sum\limits_{i=1}^n i^2 = O(n^2) $

Prove or disprove: $$\sum_{i=1}^n i^2 = O(n^2) $$ If we want to prove this, find some summation that we know the $ O(n)$ runtime for, and is $ O(n^2) $ or smaller. Otherwise, we could disprove ...
1
vote
1answer
179 views

An issue with approximations of a recurrence sequence

By trying to give an approximation to a given recurrence sequence I encountered a problem. To be more precise I have a method but it fails if the right condition is not met and I wonder how I should ...
1
vote
1answer
204 views

Exponential decay of Heat equation solution

I'm refereeing a paper and the authors go to great lengths to prove the following fact. Let $W(t,x)$ be the solution to the linear heat equation on the half-line: $\partial_t W = D \partial_{xx} W $, ...
4
votes
1answer
118 views

Iterated function?

$$f(n) = \frac{n}{\lg n}$$ $$g(n) = \min (i \ge 0: f^i(n)\le 2)$$ In other words, $g(n)$ is the number of times $f(n)$ needs to be iterated to reduce $n$ to 2 or less. What's a tight bound on ...
2
votes
1answer
64 views

simplifying an asymptotic expression

I have this expression in a statistics book, namely $nh(f(x) +o(1)+O_p(1/\sqrt{nh}))$. Where $f$ is a density function. Now, this expression is equal to $nhf(x)\{1+o_p(1)\}$. Note, that $n\to ...
1
vote
1answer
79 views

Why is it okay to do this?

I am studying asymptotic recurrences for algorithms, and the book says: $$T(n) = 2T(n/2) + \Theta (n)$$ is technically $$T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + \Theta (n)$$ for an ...
1
vote
3answers
101 views

Is it possible to prove from the definition of big $O$ that $5n^3+7n+1$ is $O(n^3)$?

Is it possible to prove from the definition of big O that $5n^3+7n+1$ is $O(n^3)$? Can this be generalised to any case where you have to (and what is the procedure for working it out?) I guess the ...
3
votes
2answers
2k views

Understanding big O notation

I'm not a mathematician by any stretch and I'm trying to translate some maths terms into simple maths terms. Please don't laugh, I do consider this complicated! The equations in question are ...
7
votes
4answers
328 views

Sum of kth roots ($\sum\sqrt[k]{m}$)

I'm trying to find an asymptotic to $$S(n) = \sum_{k=1}^n\sqrt[k]{m}$$ From computational tests, it seems to grow nearly as slowly as $n$. However even $$\sum_{k=1}^\infty\sqrt[k]{m}-1$$ diverges (for ...
2
votes
0answers
104 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 ...
0
votes
1answer
33 views

Ignoring exponential terms in asymptotic matching of two point boundary value ODE

So I'm not sure how much background I need to give to set up this question. But in my lecture notes I have that $e^{-\eta / \epsilon^{1-\alpha}}$ can be ignored where $\epsilon << 1$ and $0 ...
1
vote
1answer
55 views

asymptotic behavior of the solution to an ODE

Given $$y(t) = \frac{d_2 y_0 e^{d_2 t/\epsilon}}{d_2-\epsilon \, d_1 y_0 (e^{d_2 t/\epsilon}-1)}$$ I think that $y = O(1/\epsilon) $ as $\epsilon \to 0$. But as this is important for what I am doing ...
3
votes
1answer
76 views

Asymptotics of a solution

Let $x(n)$ be the solution to the following equation $$ x=-\frac{\log(x)}{n} \quad \quad \quad \quad (1) $$ as a function of $n,$ where $n \in \mathbb N.$ How would you find the asymptotic behaviour ...
10
votes
4answers
407 views

Singular asymptotics of Gaussian integrals with periodic perturbations

At the bottom of page 5 of this paper by Giedrius Alkauskas it is claimed that, for a $1$-periodic continuous function $f$, $$ \int_{-\infty}^{\infty} f(x) e^{-Ax^2}\,dx = \sqrt{\frac{\pi}{A}} ...
2
votes
1answer
157 views

Almost sure convergence problem

I'm working on a problem in which I should prove "almost sure" convergence for a sequence of random variables. I'm using Borel-Cantelli lemma to prove it. Here is the question and my solution - I ...
11
votes
1answer
2k views

Derivation of asymptotic solution of $\tan(x) = x$.

An equation that seems to come up everywhere is the transcendental $\tan(x) = x$. Normally when it comes up you content yourself with a numerical solution usually using Newton's method. However, ...
6
votes
1answer
92 views

Simplify $O(n^k/2^n)$

In one of my complexity analysis, I came up with $O(n^k/2^n)$, where $k$ is a fixed number and $n$ is the size of the data. However I rarely see a big-O written as this. Is there a way to even further ...
1
vote
1answer
51 views

Proof $(n^2 + 1)$ in $\Theta(n^3 - 2n - 3)$

I trying resolve this problem, but the first equation have 3 terms and the second equation have 2 terms. I don't know how to resolve this problem. Any idea?
1
vote
1answer
80 views

Question on Convergence in Probability

I appreciate if you could guide me on this question: Assumptions: $X_n \rightarrow^p c$: $X_n$ convrges in probability to a constant c. g(.) is any function that satisfies: $$\text{if } a_n - c = ...
0
votes
1answer
91 views

Summing ratio of partial sums of binomial coefficients

I would like to approximate the following when $n \gg k$. $\sum_{y = k + 1}^n \frac{\sum_{m = 0}^{k - 1} {y - 2 \choose m} (y - 1)}{\sum_{m = 0}^k {y - 1 \choose m}}.$ The formula can be re-written ...
23
votes
3answers
3k views

Prove that this function is bounded

This is an exercise from Problems from the Book by Andreescu and Dospinescu. When it was posted on AoPS a year ago I spent several hours trying to solve it, but to no avail, so I am hoping someone ...
0
votes
1answer
647 views

Is the function $\lceil\lg \lg n\rceil!$ polynomially bounded?

I'm totally lost so please be really explicit in your answers. Thanks for the help. Polynomially Bounded: $f(x)$ is polynomially bounded if for some constants $c$, $a$ and $x_0$, $$f(x) \le cx^a$$, ...
14
votes
3answers
232 views

Sufficient bound to conclude limit has certain value. $\lim {\left( {\int_0^1 {{{dx} \over {1 + {x^n}}}} } \right)^n}=\frac 1 2 $

I am trying to show that $$\lim {\left( {\int\limits_0^1 {{{dx} \over {1 + {x^n}}}} } \right)^n}=\frac 1 2 $$ Now, this can be done as follows. Using $x\mapsto x^{-1}$ we get that $$\int\limits_0^1 ...
2
votes
1answer
1k views

$f(n) = O(g(n))$ implies $g(n) = O(f(n))$

How do I prove/disprove $f(n) = O(g(n))$ implies $g(n) = O(f(n))$? I got to $f(n) \le c * g(n)$ easily enough from the definition of Big O, but I'm not sure how to get to $c*f(n) \ge g(n)$.
11
votes
0answers
358 views

Asymptotic related to the infinite product of sine

The amount is somewhat complicated ($x$ is a constant): $$S_n=\sum_{k=1}^n\ln\left(1-\frac{\sin^2\big(x/(2n+1)\big)}{\sin^2\big(k\pi/(2n+1)\big)}\right)\tag{*}$$ I want to enrich my handy powerful ...
1
vote
0answers
41 views

expected value tree structure

I'm trying to do a run-time analysis of an algorithm. The idea is a tree structure is created where any node can have two children. At each iteration of the algorithm there's a 50% chance that a node ...
0
votes
1answer
183 views

Upper bound of function including Pochhammer symbol

How can I find the upper bound of $$\left\vert\frac{(c+1/2+\lambda)_{n}}{\lambda^{n}}\right\vert,\quad\text{where}\quad(c+1/2+\lambda)_{n}=\frac{\Gamma(c+1/2+\lambda+n)}{\Gamma(c+1/2+\lambda)}$$ and ...
5
votes
1answer
189 views

Snags when discovering the asymptotic behavior of an integral

I have trouble in discovering the asymptotic behavior (i.e, the asymptotic expansion) of the following integral: $$\newcommand\abs[1]{\left\lvert#1\right\rvert} \int_0^{\pi/2}\frac{dx}{1+(n\pi+x)\sin ...
3
votes
1answer
98 views

Asymptotics for infinite sum with erf

I'm interested in approximating the infinite sum $$ \sum_{i=1}^\infty Z\left(\frac{\alpha i\pm1}{\beta}\right) $$ where $\alpha,\beta$ are constant and $$ Z(a\pm ...
1
vote
1answer
25 views

Asymptotic Approximation and Sign Convention

When I write the asymptotic approximation of a function, does the sign convention matter? i.e. suppose I have (though the formula might not make sense) $$f_n(x)=x^2+\dots-O(n),$$ If my function is ...
1
vote
4answers
117 views

Error in “proof” of $n^2 \in O(n)$.

I need some help. I have homework: I need to disprove that $f(n^2)$ belongs to $O(n)$. Why in question $n^2 = (n-1)^2+2n-1$? It must be $(n-1)^2-2n+1$. Am I right?
0
votes
1answer
39 views

Are these two definition equivalent?

$f(n) = \mathcal{o}(g(n))$ if for any constant $c$, there exists some constant $n_0$ such that $0 \le f(n) \le cg(n), n \ge n_0 $ $f(n) = \pi(g(n))$ if for any constant $c$, there exists ...
1
vote
0answers
70 views

Prove or disprove asymptotic relation of two sets

I am looking for a while to prove or disprove: (preparing for finals) O(f(n)-g(n)) ⊂ |O(f(n)) - O(g(n))| where || is absolute value. Note that ⊂ is needed and not ⊆ I assumed the a subtraction ...
10
votes
8answers
1k views

Limit of $\frac{\log(n!)}{n\log(n)}$ as $n\to\infty$.

I can't seem to find a good way to solve this. I tried using L'Hopitals, but the derivative of $\log(n!)$ is really ugly. I know that the answer is 1, but I do not know why the answer is one. Any ...
2
votes
1answer
164 views

How to interpret little-o notation in an exponent.

The definition for the little-o notation that I am using is the following: We write $f(n)=o(g(n))$ if $|f(n)|\leq c_ng(n)$, where $(c_n)$ is a sequence such that $c_n\to 0$ as $n\to\infty$. With this ...
1
vote
1answer
221 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
1answer
63 views

Solve the recurrence $T(n) = T(\log_2 n) + 13n$

I have the following recurrence relation $$T(n) = T(\log_2 n) + 13n.$$ I believe in order to solve the equation I need to determine the height of the tree. $$T(n) \to T(\log_2 n) \to ...
2
votes
2answers
55 views

Prove the following: Product of Roots

$1^{(1/1)} \cdot 2^{(1/2)} \cdot 3^{(1/3)} \cdot 4^{(1/4)} \cdot 5^{(1/5)} $.... diverges well I don't really know if it does but my gut tells me it does: I can take the log of this product to ...
12
votes
2answers
406 views

Asymptotics of the sum of squares of binomial coefficients

We are trying to estimate the cardinality $K(n,p)$ of so-called Kuratowski monoid with $p$ positive and $n$ negative linearly ordered idempotent generators. In particular, we are interesting in the ...
1
vote
1answer
140 views

Integral of smooth function

Another prelim problem: Suppose that $f(x,y)$ is a smooth function defined on $\mathbf{R}^2$. Prove that $$ \int_{x^2+4y^2\leq r^2}f(x,y)\,dx\,dy = ar^2+br^4+O(r^5) $$ Express $a$, and $b$ in terms ...
3
votes
1answer
368 views

Subtraction of Big $O$'s

So we were asked to prove something in class, but I can't understand the following expression: What is $O(n^2)-O(n^2)$? I understand big O notation, but what I don't understand is the ...
1
vote
1answer
57 views

Integral representation of a function

Here is another Prelim problem from Advanced Calculus. For $t>0$ and $D>0$ define $g(x,t)$ by $$ g(x,t)=\frac{1}{\sqrt{Dt}}\exp{\frac{-x^2}{4Dt}} $$ Now, for $f:\mathbf{R}\to\mathbf{R}$ being ...
0
votes
1answer
37 views

Big O Notation in two equations

If $a = b + O (c)$, $d = e + O (f)$ and $b > e$, can we say that $a > d$? I proceeded by substracting the two equations. I think I have not done any thing wrong. It gives $a-d=b-e + O(c-f)$ and ...
1
vote
1answer
61 views

Mixing asymptotic notations

I have a function $f(x) = g(x) - h(x)$ and I know that $g(x)=\Omega(\hat g(x))$ and $h(x)=O(\hat h(x))$. Is it well-defined to express this in asymptotic notation, as $f(x) = \Omega(\hat g(x))-O(\hat ...
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
1answer
81 views

How to prove that $\lim_{x\to \infty} x/2^x = 0$

I need to prove that $\lim_{x\to \infty} x/2^x = 0$ I'm not sure I did it right: I applied L'ôpital's rule and obtainded: $\lim_{x\to \infty} \dfrac{1}{2^x\ln2}$ and this is equal to ...
1
vote
0answers
52 views

What is the relationship between singularities for complex times and high frequency asymptotics?

As said in a paper I am reading on p 2677 in the text directly above FIG3, this should be a standard result about Fourier transforms of analytic functions. In the paper the authors use these methodes ...
1
vote
1answer
55 views

How do we determine as to how long we should sum an asymptotic series of a function to get the answer correct up to a particular precision?

As an example, consider the asymptotic expansion for polygamma function . What should be the min value of 'k' in the equation to get the answer correct upto a particular precision, say pth. Is there ...