Questions involving asymptotic analysis, including growth of functions, Big-O notation, Big-Omega and Big-Theta notations.

learn more… | top users | synonyms (1)

0
votes
1answer
384 views

Prove: $\theta(n^2)+O(n^3)\subset O(n^3)$

I believe that my understanding of this question is incorrect, so any help would be appreciated. The Question: Prove: $\theta(n^2)+O(n^3)\subset O(n^3)$ Note that for this problem, you are proving ...
2
votes
2answers
404 views

Using Master's Theorem with $f(n) = \lg^2 (n)$

This is a homework question about using Master's theorem, and I can't seem to wrap my head around this question: $$T(n)=2T\left(\frac{n}{3}\right)+\lg^2(n)$$ I've tried to apply the Master's ...
0
votes
1answer
37 views

Asymptotic coefficients of generating function $\frac{F(z)}{G(z)}$

I have the OGF in form of $\frac{F(z)}{G(z)}$, both $F(z), G(z)$ are polynomial expression and relatively prime. Do we have the systematic way to estimate $[z^n]$? I know that we can estimate ...
0
votes
2answers
734 views

Proof of $\Theta (n^2) + O(n^3) \ne O(n^3)$

This is a homework question. I have proved before that the sum of the terms on the left-hand-side are a subset of $O(n^3)$, but I have not proved that the two terms are not equal (or whether that was ...
0
votes
1answer
45 views

Analysis of the limiting behavior of a certain expression

Apologies in advance if this is too easy of a question, but as an engineer, I am out of my depth. I am interested in the conditions under which the following expression approaches to $0$: $$1 - ...
1
vote
1answer
79 views

Asymptotic bounds. What software to use?

For a pair of expressions ($A,B$), I need to determine whether $A$ is upper asymptotic, tight bound, or lower asymptotic of $B$. For example: $$A = n^{\log(c)}$$ $$B = n^{sin(n)}$$ What (free) ...
0
votes
2answers
379 views

Big-O Induction

In my Algorithms course, our first assignment is a set of induction problems. I learned (very poorly) how to do this in my discrete mathematics course two years ago, but it wasn't a very comprehensive ...
1
vote
0answers
64 views

function defined as an integral involving Bessel functions

i need to analyze a function of the form $$F(x,y) = \int_0^{1} e^{-(1+s)\alpha x}\sinh((1-s)\beta y) I_0(\sqrt{(x^2-y^2)s}) ds $$ Where $I_0$ is the modified Bessel function. $x>y$ always. ...
2
votes
1answer
184 views

Asymptotics for the divisor function

I am attempting to understand Tao's post of 23 September 2008 given here concerning the divisor bound. My troubles are when he uses the big-O notation in proving what he lists as bound (4) $$ d(n) ...
1
vote
2answers
122 views

How is how $O(\log n)$ is a subset of $O(n^b)$?

This is an excerpt from a textbook I am reading: A number of useful shortcuts can be applied when using asymptotic notation. First: $O(n^{c_1}) \subset O(n^{c_2})$ for any $c_1 < ...
2
votes
1answer
58 views

Showing that $\frac{1}{(1-\frac{\pi}{\sqrt{6n}})^n} = O(e^{\pi\sqrt{n/6}})$

Here's a small introduction on what I am doing skip to the %%%%%%%%%% if you just want the question. Definition: We say that $f(z) << g(z)$ if $|f(z)| \leq |g(z)| \quad \forall z \in D$. In ...
2
votes
1answer
191 views

Asymptotic Expansion of a Two Variable Function

How is the double asymptotic expansion defined? I can't seem to find it anywhere. Suppose $$f(x)\sim \sum_{n=0}^\infty a_n\phi_n(x)$$ as described in the Wikipedia aritcle. How is then for ...
3
votes
2answers
70 views

How to find an approximate values of rational function $f(x)$ for large $x$, neglecting $\frac{1}{x^4}$ and successive terms?

This is the function that I want to find an approximate value for it neglecting $\displaystyle \frac{1}{x^4}$ and successive terms $$ f(x)=\frac{25x}{(x-2)^2(x^2+1)}. $$
3
votes
0answers
57 views

Verifying an integral identity related to asymptotic homogenization of an elliptic partial differential equation

Background I'm reading Hornung (1997)'s Homogenization and porous media, pg 3: We study a family of [1D] problems, indexed by the scale parameter $\epsilon=\frac{1}{n}$, namely, ...
3
votes
1answer
55 views

Runtime Analysis, Coefficients in logarithms? Ignorable?

I had a question regarding when we can ignore constants during Big O analysis. If I had $f(n)=\log5x$ and $g(n)=\log100x$, would the constants $5$ and $100$ be ignorable when considering $n \to ...
0
votes
1answer
36 views

Behavior of the following function at $x=0$ singularity

I am trying to do the following integral: \begin{equation} \int\frac{1}{x^{2p}(x-1)^{2q}}\,\mathrm dx \end{equation} for positive $2p$ and $2q$. I want to understand how does this function blow up ...
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
1answer
65 views

How to write this in big O notation?

I have a function $f(m,n)$ for which there exists a constant $\alpha<2$ such that, for fixed $m$, as $n\rightarrow\infty$, we have $f(m,n)\leq\alpha\sqrt{m/n}$, and for fixed $n$, as ...
0
votes
1answer
216 views

Asymptotic notation meaning in transitive relation

I'm attempting to prove the transitive relation on $\theta$ and I'm having trouble understanding the meaning of one of the symbols used. Here is the transitive relation: $f(n) = \theta(g(n)) ...
1
vote
0answers
86 views

Solution by of nonlinear equation

$$\frac{\partial^2 u}{\partial t^2} - \frac{\partial^2 u}{\partial x^2} + \sin u = 0$$ From the sine-Gordon equation we can easily solve, \begin{equation} \phi(x) = \pm 4 \tan^{-1}\left[e^{\frac{x-t ...
0
votes
1answer
41 views

vertical asymptotes of (limit of |x-3|/(|5-x|-|1-x|) x->3-)

vertical asymptotes of (limit of |x-3|/(|5-x|-|1-x|) x->3-) As the title said I'm not sure whether this equation have vertical asymptotes or not ...
2
votes
1answer
77 views

Limit of a Permutation: $P(N,n)$ for $n\ll N$

I'm trying to prove that, for $N\gg n$, $P(N,n)=\frac{N!}{(N-n)!}\approx N^{n}$ I've tried two approaches, 1 ...
0
votes
2answers
85 views

For $f(n) = \log n$ and $g(n) = n^c$, where $0 < c < 1$, is it always true that $f$ is $O(g)$?

In complexity analysis, basic functions you encounter are functions like $f_1(n) = \log n$, $f_2(n) = n^2$ and $f_3(n) = n^3$. It is fairly obvious to me that $f_1$ is $O(f_2)$ and $O(f_3)$, but it is ...
2
votes
0answers
145 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 ...
0
votes
3answers
47 views

$c^3 \ll l^3$ prove that $\sqrt{l\over{l+c}}+\sqrt{l \over{l-c}}=2+{3c^2\over 4l^2} $

If $c^3$ is negligible compared to $l^3$, how may I prove that $$\sqrt{l\over{l+c}}+\sqrt{l \over{l-c}}=2+{3c^2\over 4l^2}?$$ This might be a problem involving binomial series.
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 ...
3
votes
2answers
147 views

On proving the convergence of $1/n^2\sum_{1\le k\le n}\varphi(k)$

Let $$\Phi_n=\frac{1}{n^2}\sum_{k=1}^n\varphi(k).$$ How one can show that $\Phi_n$ is convergent sequence? (Here, $\varphi$ denotes the Euler's totient function.) And please, without any monster ...
0
votes
1answer
42 views

Transforming a sequence of i.i.d. variables so that its asymptotic distribution is non-degenrate

Suppose $X_1,X_2,\cdots$ are i.i.d. $U(0,\theta)$ random variables. Can you suggest a function $h$ of $X_1,\cdots,X_n$ and constants $a_n$ and $b_n$ such that ...
0
votes
0answers
40 views

Testing hypothesis about variance of non-normal population

Let $X_1,X_2,\cdots$ be i.i.d. from a distribution $F$ with mean $0$ and unknown variance $\sigma^2$ and having four moments. A common test for testing $H_0:\sigma^2=1$ vs $H_1:\sigma^2>1$ is to ...
5
votes
1answer
579 views

Asymptotic correlation between sample mean and sample median

Suppose $X_1,X_2,\cdots$ are i.i.d. $N(\mu,1)$. Show that the asymptotic correlation between sample mean and sample median (after suitably centering and renormalization) is $\sqrt{\frac{2}{\pi}}$.
3
votes
2answers
171 views

When does L'Hopital's rule pick up asymptotics?

I'm taking a graduate economics course this semester. One of the homework questions asks: Let $$u(c,\theta) = \frac{c^{1-\theta}}{1-\theta}.$$ Show that $\lim_{\theta\to 1} u(c) = \ln(c)$. Hint: ...
1
vote
1answer
255 views

Can anyone derive the formula for the expansion $(x + \Delta x)^{n}$ that uses Big O notation? [duplicate]

There is a formula that describes this expansion using big O notation, I'm very curious on how this is derived. I also understand that the order term may very depending on what $\Delta x$ approaches ...
0
votes
1answer
269 views

Explanation of the binomial theorem and the associated Big O notation

I'm currently following the MIT Single Variable lectures online and the professor states that the binomial theorem for the expansion $(x + \Delta x)^{n} = x^{n} + nx^{n-1}\Delta x + O((\Delta ...
4
votes
1answer
3k views

Upper bound for $T(n) = T(n - 1) + T(n/2) + n$ with recursion-tree [duplicate]

I'm reading through Introduction to Algorithms, 3rd ed. and I got stuck on the following recurrence (exercise 4.4-5): $$T(n) = T(n - 1) + T(n/2) + n$$ The exercise asks you to find the upper bound ...
4
votes
2answers
262 views

Asymptotic expansion of a function $\frac{4}{\sqrt \pi} \int_0^\infty \frac{x^2}{1 + z^{-1} e^{x^2}}dx$

How to find the asymptotic expansion of the following function for large values of $z$. $$f_{3/2}(z) = \frac{4}{\sqrt \pi} \int_0^\infty \frac{x^2}{1 + z^{-1} e^{x^2}}dx $$ I have to get something ...
1
vote
1answer
60 views

Repeated Bernoulli Trials, Wins-Losses

Consider $$X(t)=\mbox{Number of wins} - \mbox{Number of losses}$$ for $t$ Bernoulli($\theta$) trials. I calculated that $$P(X(t) = x) = {t \choose (t-x)/2} \theta^{\frac{t+x}{2}} (1- ...
4
votes
1answer
70 views

Is there a “natural” subsequence of positive integers $k_1 < k_2 < \ldots$ such that $\sum_{i=1}^n \frac{1}{k_i} = \Theta (\log \log \log n)$?

The harmonic series partial sums grow like $\log n$, and the sum of inverses of the first $n$ primes grows like $\log \log n$. Is there an example of a "nautral" subset of the positive integers (say ...
3
votes
5answers
459 views

Provide an algorithm $O (n ^ 3 \log n)$, any example?

Provide an algorithm computing performance $O (n^3 \log n)$. Your algorithm should contain only simple operations. Any idea of how to approach this problem?...I am studying for the computer science ...
4
votes
1answer
362 views

Can a curve be an asymptote?

$f(x)=x^3+\frac{3}{x-1}$ This was the question given to me.I replied that $f(x)$ will have only a single vertical asymptote of $x=1$. My teacher told that there'll be be two asymptotes.One is the ...
8
votes
4answers
537 views

The asymptotic expansion for the weighted sum of divisors $\sum_{n\leq x} \frac{d(n)}{n}$

I am trying to solve a problem about the divisor function. Let us call $d(n)$ the classical divisor function, i.e. $d(n)=\sum_{d|n}$ is the number of divisors of the integer $n$. It is well known that ...
5
votes
2answers
436 views

Inverse of sparse matrix is not generally sparse

I have a question regarding inverse of square sparse matrices(or can be restricted to real symmetric positive definite matrices). I encountered several times the web pages which states that the ...
1
vote
1answer
37 views

Limiting Distribution of the given function

Can someone please help me in finding the limiting distribution of $$\frac{n(X_1X_2 + X_3X_4+\cdots+X_{2n-1}X_{2n})^2}{(X_1^2 + X_2^2+\cdots+X_{2n}^2)^2}$$ where $X_i$ are iid standard normal ...
2
votes
3answers
104 views

Need an asymptotic function that's going to have a specific shape

I'm looking for a function y = f(x) that grows quickly at first, and slowly later, asymptotically approaching 100. I need it to hit certain specific points... What I need is: ...
2
votes
1answer
78 views

Asymptotic solving of a hyperbolic equation

The solition and anti-solition nonlinear equation is given as: My problem is that, how do we get the next equation after considering asyptotic behaviour? Resource: (solition) at page 38
25
votes
1answer
486 views

Power towers: to infinity and all the way back

In the following, let $n$ be a positive integer, all other variables be real (furthermore, $a>1$), all functions be real-valued, and logarithms of negative arguments be undefined. Let ...
4
votes
0answers
248 views

An entire function of strict order 2

Here is a problem from Stein and Shakarchi Complex Analysis, can somebody help me to solve it? I guess we can use Phragmen-Lindelof theorem but I don't know the exact way. Suppose $f(z)$ is an entire ...
10
votes
3answers
288 views

Estimate $\displaystyle\int_0^\infty\frac{t^n}{n!}e^{-e^t}dt$ accurately.

How can I obtain good asymptotics for $$\gamma_n=\displaystyle\int_0^\infty\frac{t^n}{n!}e^{-e^t}dt\text{ ? }$$ [This has been already done] In particular, I would like to obtain asymptotics that ...
2
votes
1answer
78 views

asymptotic behaviour of coefficients in nonnegative matrix iteration

Let $A$ be a square matrix with nonnegative integer coefficients. Is there a simple way to prove that there is a "period" $d$ such that for all $0\leq r<d$, the coefficient $a_{i,j,n}$ at position ...
3
votes
1answer
70 views

Prove that $F_{x^{n+1}} \sim 5^{\frac{x-1}{2}}F_{x^n}^x \forall x,n \geq 1$, holding either variable constant while the other goes to infinity

I noticed from looking at the prime factorizations of some Fibonacci numbers that all those with an index equal to a power of 5 divided that power of five, a property not guaranteed by the strong ...
5
votes
1answer
192 views

Showing a Lebesgue integral exists, while another doesn't.

Consider $$f_p(x)=x^p \exp\left(-x^8\sin^2x\right)$$ I have to show that $f_2\in\mathscr L(0,+\infty)$ whilst $f_3\notin \mathscr L(0,+\infty)$. Now, I am looking at the case $p=2$. The problematic ...