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
0answers
24 views

Analytic function with inconsistent asymptotic behaviour on rays

Consider an function $f$, defined continuously on the closed upper half plane, and analytic on the upper half plane. Going along any ray from the origin that go strictly up (ie. not along the real ...
5
votes
1answer
143 views

Good resource/exercises for learning asymptotic analysis?

I am studying asymptotic methods right now; things such as mellin transform, inverse mellin transform, saddle point method, laplaces method, etc... and I get very frustrated because I can't get very ...
1
vote
1answer
66 views

Why is $(\log n)^3\in O(\sqrt n)$?

Comparing the order of growth of the two functions by taking a limit and using l'hospitals rule, it seems that $\sqrt{n}$ should be O($log^3n$). Here are the steps I took: $$\lim_{n \to ∞} ...
0
votes
0answers
22 views

Laplace's Method modifications

I was wondering if there is a "Laplace's Method" to estimate, as $n \to \infty$, integrals of type $$ I_n = \int_0^\infty e^{nh(x)}g(nx) \, dx $$ where $g$ is a smooth function, that converges to a ...
2
votes
0answers
38 views

Asymptotic of a real double serie on $\mathbb{Z}$

I am interested by a real sequence $\{a_n\}_{n\in\mathbb{Z}}$ as $\sum_{n\in\mathbb{N}}\left(\vert a_n\vert + \vert a_{-n}\vert\right)$ converges. I want to find the asymptotic behavior of this ...
1
vote
0answers
13 views

Integral of product of Hermite functions with rescaled weights.

Let $$h_{k}(x)=c_{k}(-1)^k e^{\frac{x^2}{r^2}}\frac{d^k}{dx^k}e^{-\frac{x^2}{r^2}}$$ be the standard Hermite polynomials, rescaled with a given parameter $r>0$. The normalizing constant ...
3
votes
0answers
56 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, ...
1
vote
0answers
22 views

Proof that difference equations as asymptotic to their differential analog.

Given a difference equation $a_{n+k}=f(a_n,a_{n+1},\dots,a_{n+k-1})$, we can classify $n=\infty$ as an ordinary, regular singular, or irregular singular point by classifying $x= \infty$ in the ...
5
votes
2answers
76 views

How to show that $\sum_{x=1}^\infty \prod_{i=1}^{x-1} (1-i/n) \sim \sqrt{\frac{\pi n}{2}}$?

How can one show that asymptotically $$\sum_{x=1}^\infty \prod_{i=1}^{x-1} \left(1-\frac{i}{n}\right) \sim \sqrt{\frac{\pi n}{2}} \; ?$$ A non rigorous argument is to say that for large $n$, ...
0
votes
1answer
41 views

Big O - arithmetic rules

I need to prove the following statement: $O(f(n)g(n))=f(n)O(g(n))$ At first I thought the statement is false but apparently it is true. How can I prove it?
4
votes
1answer
71 views

How to show $\sum_{i=1}^{n-1} \frac{i(n-2)!}{(n-1-i)!n^{i+1}} \sim 1/n$

How can one compute the large $n$ asymptotics of $$\sum_{i=1}^{n-1} \frac{i(n-2)!}{(n-1-i)!n^{i+1}}\;?$$ My guess is that it is $1/n$ but I don't know how to show that.
0
votes
1answer
29 views

Big oh proof for a(n) using big oh hierarcy

So I'm given the following big-oh hierarchy (each sequence is big-oh of any seqeuence to its right.) $1$, $\log_2{n}$, ... , $\sqrt[4]{n}$, $\sqrt[3]{n}$, $\sqrt{n}$, $n\log_2{n}$, $n\sqrt{n}$, ...
4
votes
1answer
116 views

Growth of ratio based on sum of squared binomial identity

It is a well-known identity that $$\binom{n}{0}^2+\binom{n}{1}^2+\cdots+\binom{n}{n}^2=\binom{2n}{n}.$$ By symmetry of the binomial coefficients, this means the ratio ...
13
votes
5answers
1k views

Is there any nonconstant function that grows (at infinity) slower than all iterations of the (natural) logarithm?

Is there any nonconstant function that grows at infinity slower than all iterations of the (natural) logarithm?
1
vote
1answer
29 views

Asymptotic relation between specific binomial coefficient and exponential function

I need to determine the asymptotic relationship between the functions: $$f_1(n)={n\choose{\lfloor{n\over{2}}\rfloor}}, f_2(n)=7^{\sqrt{n}}$$ (I'm going to just assume $n$ is always even.) I've ...
1
vote
2answers
56 views

Finding an approximation for the difference of $a_n = \frac{1}{1+a_{n-1}}$ and it's limit.

I've got the recurrence $\displaystyle{a_{n} = {1 \over 1 + a_{n - {\tiny 1}}},\ }$ for $0 < a_{0} < 1 $ which has the solution $\displaystyle{\alpha = {\,\sqrt{\, 5\,}\, - 1 \over 2}}$ I am ...
0
votes
0answers
13 views

Asymptotics and function composition

In the following question: Big O and function composition It is explained that if $a, b, c, d$ are functions and $a = O(c), b = O(d)$ it doesn't mean that $a ∘ b = O(c∘d)$. However, what if we allow ...
5
votes
2answers
389 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 ...
0
votes
0answers
12 views

GRAM series and Logarithmic integral

due to the prime number theorem wouldn't we expect that the prime number counting function admits the approxiamtion $$ \pi (x)= \gamma +loglog(x)+ \sum_{n=1}^{\infty} \frac{log^{n}(x)}{n.n!.\zeta ...
2
votes
1answer
60 views

Number of words not having a subword of length k with only one letter

Let $f_k(n,t)$ be the number of words of length $t$ over the alphabet $\mathcal{A} = \{1,\ldots,n\}$ such that no word contains $i^k$ as a substring for $i \in \mathcal{A}.$ I am looking to find the ...
1
vote
0answers
35 views

Order of magnitudes comparisons

I need your help with the following. I need to determine how to order (functions) the following : \begin{align} &f(x)=(x/2)^{(x/2)} \\ &g(x)=x! \end{align} Note: I got both of them are ...
0
votes
0answers
47 views

Big-O Notation Division

There was a similar thread on this question, but I am still unsure about the answer. I am asked to show, $$ \frac{e^{(r-q)h}-e^{-\sigma\sqrt{h}}}{e^{\sigma\sqrt{h}}-e^{-\sigma\sqrt{h}}} = ...
2
votes
1answer
92 views

Corollaries of Green-Tao Theorem?

there is already a good thread which discusses some corollaries of the Green-Tao Theorem, here: Constructing arithmetic progressions The question I was wondering about is of a similar flavor but ...
-1
votes
1answer
23 views

big $\Theta$ question dealing with $\log_2{n}$ and $\log_{10}{n}$

Show that $\log_{10}{n} = \Theta(log_2{n})$. I know that I have to show that 1) $\log_{10}{n} = O(\log_2{n})$ show: $\log_{10}{n} \le C * \log_2{n}$ and 2) $\log_2{n} = O(\log_{10}{n})$ show: ...
0
votes
0answers
19 views

Big theta question

Find a number $a$ with $s(n) = \Theta(a^n)$ for $s(n) = 1^{(n^2+200n+5)}$. I worked out that $a = 1$ and that $1^{(n^2+200n+5)} \le C * 1^n, C = 1, n = 0.$ So long as n $\ge$ 0 the right-hand side ...
0
votes
1answer
21 views

Big oh / big theta proof for the following

Find a number $a$ with $s(n) = \Theta(a^n)$ for $s(n) = (\log_2{10})^{(n-3)}$. I'm not quite sure how to proceed. I was having problems with another problem trying to figure out what it means to ...
0
votes
2answers
44 views

Why is Wolfram missing so many oblique asymptotes? (Not only about Wolfram in thread)

Few days ago I made a post, and to be frank I'm not sure if I'm even having this question in the right forum. But I'm also looking for information on if my thoughts are correct. Observe this little ...
0
votes
1answer
35 views

Proving big oh for a function

Find a $C$ and $k$ such that $\sqrt{n^2 - 1}$ = $O(n^k)$. My professor has stated that there are two different $k$'s. One from the problem statement and one from the definition of big-oh. I know that ...
0
votes
3answers
62 views

Finding the limit of: $\lim_{x\rightarrow +\infty}\left(x\arctan x-x\dfrac{\pi}{2}\right)$

$\lim_{x\rightarrow +\infty}\left(x\arctan x-x\dfrac{\pi}{2}\right)$ I just removed a lot of unnecessary text from this post. If anyone could tell me how to find this limit, without L'Hôpital's rule, ...
1
vote
2answers
92 views

Find the leading order asymptotic behaviour of the integral

$$I(x) = \int_0^{\infty}e^{-t-\frac{x}{t^2}}dt \mbox{ as } x \mbox{ tends to infinity} $$ I know this has a moveable maximum so you need to make a substitution which transforms it into the integral: ...
3
votes
1answer
25 views

Oblique asymptote for: $f(t) = \frac{t^2\arctan t}{t-4}$?

Say a function $$f(t) = \frac{t^2\arctan t}{t-4}$$ Obviously, this has a vertical asymptote at $t = 4$. However, the oblique asymptote, if there is one, I can't seem to find. What I do is I put the ...
1
vote
1answer
44 views

Calculate the leading order asymptotic behaviour (with two maxima)

thanks in advance! Calculate the leading-order asymptotic behaviour of the integral $$I(x) = \int_{0}^{2\pi} (1+t^2) e^{x \cos t} dt \mbox{ as } x \mbox { tends to infinity}$$ So far I know there ...
1
vote
1answer
40 views

Asymptotic solution to a differential equation near zero

I am trying to get the both the asymptotic solutions of the equation $y''(x)=\sqrt{x} \cdot y(x)$ as $x\rightarrow 0$. But when I put $y(x)=\exp(S(x))$ since $x=0$ is an irregular singular point, no ...
0
votes
1answer
23 views

How to prove this asymptotic bound? [closed]

Given that $0<a<b$, $f(n) \in O(n^a)$, prove that $f(n) \in o(n^b)$ (note there is a difference between big o and little o)
0
votes
0answers
14 views

Determining if f(n) is Big-O of g(n)

I'm currently learning Big-O notation but I'm having a lot of trouble understanding it. I'm working through some true/false exercises: 1) $log(k)$ is $O(k)$ 2) $klog(k)$ is $O(k^2)$ 3) $k^2$ is ...
2
votes
0answers
27 views

Number of ways to visit each cell of $n\times n$ board once

A piece lies on the upper-left corner of an $n\times n$ board. Let $f(n)$ denote the number of ways to move the pieces one step horizontally/vertically at a time, so that it visits each field of the ...
1
vote
3answers
69 views

Iterated integer-valued decimation

This question is for those who have wondered what it means to decimate an army when the number of soldiers is not a multiple of ten. I am interested in really good upper bounds on the length of a ...
0
votes
1answer
28 views

Lower bounds for an expression of two positive integers?

Can we get an approximate lower bounds for the following expression: $$\left( 1 + \frac{1}{ 2 \left( \frac{4^{nC}-1}{2^n-1} \right) } \right)^{ \frac{1}{\left( \frac{4^{nC}-2^{nC}}{2^n-1} \right) } ...
2
votes
1answer
38 views

Asymptotics of $\frac{1}{n} \sum_{ d|n } \mu{\left(\frac{n}{d}\right)} 2^d $

Define $$a(n) = \frac{1}{n} \sum_{ d|n } \mu{\left(\frac{n}{d}\right)} 2^d $$ where $\mu()$ is the Möbius function. Is it possible to find easily computable $b, c$ such that $b(n) \leq a(n) \leq ...
0
votes
2answers
40 views

Show that $3n^2 - n+4$ is $O(n^2)$

From the definition of big oh: We say that "$f(n)$ is big oh $g(n)$" if there exists an integer $n_0$ and a constant $c>0$ such that for all integers $n\geq n_0$, $f(n)\leq cg(n)$. Substituting ...
0
votes
1answer
92 views

Proof of simple relation involving near primes?

Motivation (can skip!). (*) $\sum\log n \approx n\log n-n,$ and $$\sum\log n = \sum_{p_1\leq n} \log p_1+\sum_{p_2\leq n} \log p_2+...+\sum_{p_m\leq n} \log p_m$$ in which $p_k$ are numbers comprised ...
1
vote
0answers
26 views

Calculate the leading-order asymptotic behaviour (Laplace's Method) [duplicate]

thanks in advance! Calculate the leading-order asymptotic behaviour of the integral $$I(x) = \int_{0}^{2\pi} (1+t^2) e^{x \cos t} dt \mbox{ as } x \mbox { tends to infinity}$$ So far I know there ...
0
votes
2answers
15 views

Determine the asymptotic behavior of $f(n)$ in relation to $g(n)$

$f(n)=n^\sqrt{n}, g(n)=2^n$ $f(n)=10^{\log\log n}, g(n)=\log n$ Note: $\log$ is in base 2. For section #1, I tried to evaluate the limit $\lim_{n\to\infty} \frac{2^n}{n^\sqrt{n}}$ but got stuck ...
1
vote
0answers
25 views

How to prove that a function f(x) is O(g(x)), using the definition (finding C and k)

We say that $f(x)$ is $O(g(x))$ if $$(∃C ∈ \mathbb(R)❘)(∃k ∈ \mathbb(R)❘)(∀x ∈ \mathbb(R)❘)$$ $$(x ≥ k → |f(x)| ≤ C · |g(x)|)$$ In English: We can find $C$ and $k$ so that, once we get past the “small ...
0
votes
0answers
28 views

Am I to place my trust in Wolfram on this matter? [Oblique asymptotes on a function]

So I used Wolfram to find oblique asymptotes for the following function $f(x) = 2x + 3 - \frac{1}{\ln x}$ The vertical asymptote, which Wolfram finds as well, is $x=1$. However, my method for finding ...
2
votes
3answers
462 views

big O notation with asymptotically nonnegative increasing functions

Let $f(n)$ and $g(n)$ be asymptotically nonnegative increasing functions. Show: $f(n) · g(n) = O((\max\{f(n), g(n)\})^2)$, using the definition of big-oh. I can't quite figure this out, can ...
1
vote
1answer
86 views

Find asymptotics in a given form $n=(e+o(1))^{f(s)}$

Let $p\to\infty$, $s={\binom {p^4} p}$ and $n={\binom {p^4}{p^2}}$. Find a function $f(s)$ in the following form $$\large n=(e+o(1))^{f(s)}$$ I've tried to use the followinf asymptotics for ...
0
votes
1answer
44 views

Disproving a relation between function and derivative concerning Big-O-Notation

The question is to disprove the following: Be $f$ a continuously differentiable function that maps from $\mathbb{R}\rightarrow\mathbb{R}$ and $f(x) =\mathcal{O}(x^2) $ for $x\rightarrow0$, then it ...
0
votes
1answer
59 views

$\frac{a_n - a_{n+1}}{a_n} \approx \frac{1}{n}$? (part of 2010 Putnam exam)

Given a non-negative sequence $a_n$, strictly decreasing and tending to zero, can we show that (for large $n$) $$ \frac{a_n - a_{n+1}}{a_n} \approx \frac{a_n}{na_n} = \frac{1}{n} \text{ }?$$ ...
1
vote
2answers
76 views

Solving $T(n)= 2T(n/2) + \sqrt{n}$ without master theorem (algebraically & recurrence tree)

$$T(n)= 2T(n/2) + \sqrt{n}$$ This recurrence was in a stackoverflow question, and I want to solve it without relying on the master method. The solution was given, but wolframAlpha gives a slightly ...