Questions involving asymptotic analysis, including growth of functions, Big-O notation, Big-Omega and Big-Theta notations.
1
vote
0answers
30 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
73 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 ...
1
vote
1answer
22 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$ ...
2
votes
1answer
69 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 ...
-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
77 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 ...
5
votes
1answer
60 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)$ ...
3
votes
3answers
68 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?
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 $, ...
2
votes
1answer
27 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 ...
4
votes
4answers
103 views
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 ...
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 ...
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
...
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}$.
6
votes
4answers
112 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
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
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?
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 ...
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 ...
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
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 ...
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}} ...
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.
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$$, ...
2
votes
1answer
51 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)$.
1
vote
0answers
20 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 ...
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
0answers
15 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 ...
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 ...
2
votes
1answer
31 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 ...
0
votes
1answer
37 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 ...
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?
10
votes
8answers
233 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
2answers
45 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 ...
7
votes
3answers
179 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
33 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
48 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
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 ...
1
vote
1answer
49 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
26 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 ...
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 ...
0
votes
1answer
17 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
1answer
76 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 ...
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 ...
