Questions involving asymptotic analysis, including growth of functions, Big-O notation, Big-Omega and Big-Theta notations.
1
vote
1answer
66 views
Are definitions these of Big-O notation equivalent to the standard?
This definition uses hyper-reals and nonstandard analysis.
Let $k^*(x)$ be the natural extension of $k(x)$. Let $f$ and $g$ be functions.
$f = O(g) := \frac {f^*(H)} {g^*(H)}$ is finite for all ...
2
votes
1answer
66 views
Behavior of $\Gamma(z)$ as $\text{Im} (z) \to \pm \infty$
In a paper I'm reading it states that $\displaystyle |\Gamma(z)| = |\Gamma(a+ib)| \sim \sqrt{2 \pi} |b|^{a-\frac{1}{2}} e^{-|b|\frac{\pi}{2}}$ as $\displaystyle|b| \to \infty$.
How is that derived ...
1
vote
0answers
21 views
Asymptotic growth over an interval
Given a function $f(x)$, we can define the new function
$$
A_f(t) = \limsup\limits_{x\to\infty}\ (f(x+t) - f(x))
$$
Is there a place that this transformation has been studied?
Also, given a positive ...
1
vote
1answer
21 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
100 views
-2
votes
0answers
40 views
Solve $ z= \frac{2a^2}{-4+z} + \frac{2a^4}{(-4+z)^2(-16+z)} + \cdots $.
I am trying to solve $z\in \mathbb{C}$ in terms of $a\in \mathbb{C}$, where
$$
z= \frac{2a^2}{-4+z} + \frac{2a^4}{(-4+z)^2(-16+z)} + \cdots.
$$
I plugged $z= \sum_{k=0}^\infty c_k a^k $ into the ...
3
votes
2answers
73 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 ...
4
votes
2answers
259 views
Showing that $\lim_{n\to\infty}\sum^n_{k=1}\frac{1}{k}-\ln(n)=0.5772\ldots$
How to show that $$\lim_{n\to\infty}\sum^n_{k=1}\frac{1}{k}-\ln(n)=0.5772\ldots$$
No clue at all. Need help! Appreciated!
1
vote
1answer
145 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 ...
7
votes
3answers
178 views
Asymptotic for the integral involving exponential
The integrand seems extremely easy:
$$I_n=\int_0^1\exp(x^n)dx$$
I want to determine the asymptotic behavior of $I_n$ as $n\to\infty$. It's not hard to show that $\lim_{n\to\infty}I_n=1$ follows from ...
1
vote
1answer
39 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 $, ...
5
votes
1answer
49 views
Chain rule proof
Let $a \in E \subset R^n, E \mbox{ open}, f: E \to R^m, f(E) \subset U
\subset R^m, U \mbox{ open}, g: U \to R^l, F:= g \circ f.$ If $f$ is
differentiable in $a$ and $g$ differentiable in ...
0
votes
0answers
15 views
Asymptotic recurrences?
$$T(n) = 2T(n/2) + \Theta(n), n > 1$$
$$T(n) = \Theta (1), n \le 1$$
$$G(n) = G(\lfloor n/2 \rfloor) + G (\lceil n/2 \rceil) + \Theta(n), n > 1$$
$$G(n) = \Theta (1), n \le 1$$
Prove $T(n)$ ...
4
votes
1answer
43 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 ...
3
votes
3answers
67 views
Does $n n^{1/n} =O(n)$?
I was asked does $n n^{1/n} =O(n)$ ?
I can see that the left hand side is always bigger than $n$ but how would you prove the equality is false?
2
votes
1answer
26 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
47 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
71 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 ...
2
votes
2answers
108 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
...
6
votes
4answers
110 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 ...
1
vote
1answer
43 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
17 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 ...
4
votes
0answers
88 views
What is a good asymptotic for $f_n = f_{n-1}+\ln(f_{n-1})$?
Let $f_0=2$ and $f_n=f_{n-1}+\ln(f_{n-1})$. What is a good asymptotic to the sequence $f_n$? With good I mean much better than $f_n \sim \dfrac{3n \ln(2)\ln(n)}{2}$.
1
vote
1answer
38 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 ...
1
vote
1answer
136 views
Finding Slant Asymptotes using synthetic division rather than long division
Is it possible to use repeated synthetic division (rather than long division) to find a slant asymptote for a rational function such as $\displaystyle \frac{2x^3 + 3x^2 + 5x + 7}{(x-1)(x-3)}$? It ...
3
votes
1answer
70 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 ...
9
votes
4answers
277 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}} ...
3
votes
1answer
34 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 ...
8
votes
1answer
764 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, ...
2
votes
2answers
178 views
A systematic way to estimate the cardinality of a set
Let me take the following set as an example:
\[ A = \lbrace \langle a,b \rangle \in \mathbb{N} \times \mathbb{N} : a^2 + b^2 \leq n \rbrace . \]
One approach would be to notice that $A$ is the set ...
5
votes
1answer
85 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
31 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?
2
votes
1answer
40 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
34 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 ...
-5
votes
0answers
49 views
Asymptotic expressions
Can you help me out. I need to know if the following asymptotic notations are true
$3 n^2 + 9 = \theta(n^2)$ TRUE?
$n^2 \lg n = \theta(n^2)$ TRUE?
$3^{(n+1)} = \theta(3^n)$ TRUE?
$n^3 + 25n^2 + ...
1
vote
0answers
45 views
Multivariable asymptotic analysis?
Show that $k \ln k = \Theta (n)$ implies $k = \Theta (n /\ln n)$.
Thanks for the help.
18
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
46 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$$, ...
12
votes
3answers
165 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
3answers
39 views
Polynomial bounds?
Q1: Is the function $$\lceil{\lg n}\rceil!$$ polynomial bounded?
Q2: Is the function $$\lceil{\lg\lg n}\rceil!$$ polynomially bounded?
$$\lg = \log_2$$
Polynomially bounded: $f(n)$ is polynomially ...
2
votes
1answer
50 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)$.
9
votes
0answers
224 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
19 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
84 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
129 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
51 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
17 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
98 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
31 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
14 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 ...
