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
0answers
43 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
184 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
262 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$ ...
3
votes
1answer
105 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 ...
3
votes
2answers
158 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
156 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 ...
6
votes
3answers
100 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
182 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
62 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
732 views

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

How do I prove that $2^n=O(n!)$? Is this a valid argument? ...
1
vote
1answer
77 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
114 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
97 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 ...
0
votes
1answer
31 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 ...
9
votes
1answer
267 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}$.
7
votes
4answers
309 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
54 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
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?
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 ...
2
votes
1answer
153 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 ...
1
vote
1answer
79 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
89 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 ...
2
votes
0answers
102 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 ...
10
votes
4answers
391 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
1answer
121 views

Multivariable asymptotic analysis?

Show that $k \ln k = \Theta (n)$ implies $k = \Theta (n /\ln n)$. Thanks for the help.
0
votes
1answer
517 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
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)$.
1
vote
0answers
38 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
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
0answers
62 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
0answers
347 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
153 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
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 ...
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?
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
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 ...
7
votes
3answers
300 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
126 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
325 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
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
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
36 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
185 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 ...
1
vote
1answer
54 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
60 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
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 ...
2
votes
3answers
488 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 ...
1
vote
0answers
51 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 ...
12
votes
2answers
387 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 ...