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
19 views

Proving equation using formal O(f(n)) - step by step?

I have huge problems showing whether example like this: is true or false using formal definition of Big O. How can I solve such problems step by step? I understand that formal definition of O(f(...
1
vote
1answer
35 views

Asymptotic behavior of Fourier transform and Hölder condition

I'm trying to solve this question. Following the hint, the Fourier inversion formula gives me : $$ \big| f(x+h) - f(x)\big| = \left| \frac{1}{2\pi} \int_{-\infty}^\infty \widehat{f}(\xi) e^{i(x+h)\...
4
votes
1answer
61 views

The behaviour of $\sum k^a 2^k$.

Let $a$ be a real number, I want to find a simple equivalent (or if it is possible, an asymptotic expansion) of $$\sum_{k=1}^n k^a 2^k.$$ I believe that the sum is $\sim n^a 2^{n+1}$ (tried many ...
8
votes
0answers
103 views

If $n={k^2 \choose k}$, then what is $k$?

Given that: $$n={k^2 \choose k}$$ what is $k$ as a function of $n$? So far, I have found the following approximation: $$ n \approx (k^2)^k = (k^k)^2 $$ $$ \sqrt{n} \approx k^k $$ If we take this ...
1
vote
1answer
19 views

Proof of Property of little o

I am learning some asymptotic analysis and i'm trying to prove: If $\lim_{x\to c} f(x)< \infty$ then $o(fg)=o(g)$ (as $x \to c$). So far i have proved that $o(fg)\subset o(g)$, but i am stuck on ...
0
votes
1answer
16 views

Asymptotic behavior

I very much dislike the "Big Oh" notation. It just doesn't stick in my mind. Suppose $f$ is a continuous function and $f \in \text{O}( 1/|x|^{1+\epsilon})$ when $|x| \rightarrow \infty$ and for $0< ...
2
votes
1answer
71 views

How to prove $({\log_2 x})^{n+1} \le x^n$

I want to show that $({\log_2 x})^{n+1} \le x^n$ when $n \ge 1$ and $x \ge 1$. I know that ${\log_2 x}$ can be shown to be $\lt x$ with: $x \lt 2^x$ $\log_2 x \lt x$ and obviously adding the same ...
1
vote
1answer
20 views

Proof involving the Big-O notation

I am stuck on a proof question involving the big-O notation: Prove that if $f(x)$ is $O(x^3)$ then $f(x+x^2)$ is also $O(x^3)$. I am stuck because $f(x)$ can be any arbitrary polynomial. I started ...
0
votes
1answer
29 views

Graph with both slant and horizontal asymptotes

Is there such a graph? A graph that increases at a decreasing rate with the graph approaching a slant asymptote as x decreases to negative infinity while the graph approaching a horizontal asymptote ...
1
vote
2answers
32 views

asymptotic equivalence between harmonic numbers and logarithm

I have recently learned about asymptotical equivalence, defined as $$ a(n) \sim b(n) \Leftrightarrow \lim\limits_{n \to \infty} \frac{a(n)}{b(n)} = 1$$ Now I would need to prove that $H_n \sim \ln(n)...
1
vote
1answer
27 views

Showing $\psi(x)=\theta(x)+O(\sqrt x\log x)$ for Chebyshev's function $\psi$

In my textbook, there is the following theorem: For all $x>0$, we have $$\psi(x)=\sum_{\alpha=1}^\infty\theta(x^{1/\alpha})$$ and hence $$\psi(x)=\theta(x)+O(\sqrt x\log x).$$ Here $\theta(x)=...
1
vote
1answer
39 views

Asymptotics of a series involving cos integral functions

I'm looking for the asymptotic expansion( or value ) of the following function \begin{equation} F[y,t] = \sideset{}{'}\sum_{n \in \mathbb{Z}}\text{Ci}\big[\frac{n^2}{t}\big] - \text{Ci}\big[\frac{(n+...
4
votes
1answer
70 views

Asymptotic behavior of an integral involving the gamma function

I'm trying to obtain an asymptotic large-$k$ approximation for the integral $$I(k) := e^{-k^2}\int_0^1 \frac{(1 + \xi^2)\Gamma(0, \xi^2 k^2) - 2\Gamma(0, k^2)}{1 - \xi} d\xi$$ where $\Gamma$ is the ...
2
votes
1answer
53 views

Inner solution of singular perturbation problem

Consider singular perturbation problem $$\epsilon \left[\frac{d}{dx}\left(h^3p\frac{dp}{dx}\right)\right]=\frac{d}{dx}(hp)$$ $$p(0)=p(1)=1$$ where $h(x)$ is a positive smooth function with $h(0)\ne h(...
0
votes
1answer
32 views

How to show that $f_2(n)=2^n$ grows faster than $f_1(n)=n^{\log{n}}$

The graphs of the two functions $f_1(n)=n^{\log{n}}$ and $f_2(n)=2^n$ clearly show that $f_2$ grows faster than $f_1$, but how do we mathematically prove this?
1
vote
0answers
31 views

Does asymptotic expansion of Whittaker function $W_{\lambda , \mu}(z)$ exist for $|\lambda| \to 0$?

Suppose Whittaker function $$ \tag 1 W_{\lambda , \mu}(z) $$ Does some asymptotic expansion exist for the case $|\lambda| \to 0$? I'm interested not in the case of $\lambda = 0$, but in the case of ...
0
votes
0answers
24 views

Getting tight asymptotic upper and lower bounds of combinatorical expression

$$\binom{n}{\frac{n}2}$$ I tried to do some rough estimates, but I didn't succeed at all well. Can somebody give a clue? Oh and i Forgot to mention, without Stirling formula. One thought is to do ...
0
votes
1answer
45 views

Asymptotic variance of MLE of normal distribution.

I am trying to explicitly calculate (without using the theorem that the asymptotic variance of the MLE is equal to CRLB) the asymptotic variance of the MLE of variance of normal distribution, i.e.: $$\...
1
vote
1answer
30 views

Why is $O(x^{\alpha + \epsilon}) \neq O(x^{\alpha})$ if $\epsilon$ is arbitrarily small but greater than $0$?

There are several equivalent formulations of the Riemann hypotheses that utilize the big O notation. For example, it is known that $M(x) = O\left(x^{\frac12+\epsilon}\right)$ for all $\epsilon > 0$,...
0
votes
0answers
48 views

Finding the real part of a complex function

I am trying to compute the real part of the following complex function: $$S(z) = \frac{8}{3}\sqrt{z^{-\frac{1}{2}} + z^{-1}}\left(z + z^{\frac{1}{2}}\right)$$ For context, this expression was ...
1
vote
0answers
62 views

Asymptotic behaviour of the integral

Suppose I have the integral $$ \tag 1 I\left[p\equiv -\frac{1}{2}\pm ia, z\right] \equiv \frac{1}{\Gamma(-p)}\int \limits_{0}^{\infty}e^{-xz -\frac{x^{2}}{2}}x^{-p-1}dx $$ I'm interested in asymptotic ...
1
vote
1answer
27 views

Lagerstrom-Cole equation

Consider this boundary value problem $$\epsilon u''+uu'-u=0,\quad u(0)=A\in\mathbb{R},\quad u(1)=3.$$ This differential equation is known as Lagerstrom-Cole equation. I trying to construct asymptotic ...
0
votes
1answer
16 views

Why asymptotic notation trying to get rid off multiplicative constants?

When I reading through an article about asymptotic notation, there is a sentence - "For large enough inputs, the multiplicative constants and lower-order terms of an exact running time are dominated ...
1
vote
1answer
44 views

Is it true $ 2^{2^n} = O(2 ^n )$?

I have some problem to solve this question. Intuitively, I think not, but I'm not sure. If a log the lelf a have $2^n \log2 <= 2^n$ That's ok ?
3
votes
1answer
47 views

Asymptotics of this HyperGeometric Function

I have a function $$f(x)=x^{2m}\text{ }_2F_1\left(\frac{1}{2},-m;\frac{3}{2};-\frac{1}{x^2}\right)$$ where $x>0$. I am interested in asymptotics in the two extreme limits: $$\lim_{x\rightarrow 0} ...
0
votes
0answers
26 views

Resolving Zeros in Product of items in list.

Given the formula: $\sqrt [ 1/N ]{ \prod _{ n=1 }^{ N }{ { P }_{ n } } } $ where ${ P }_{ n }$ is a list of real numbers, e.g. [0.4, 0.3, 0.2, 0.1] And the ...
3
votes
0answers
72 views

How close are we to knowing the rate of convergence to $0$ of $\prod_{p\le x}(1-1/p)^{-1}-e^\gamma\log x $?

This is a question related to an earlier one of mine, which I may answer myself eventually, as I have learnt more about the topic. Despite what one can read on the MathWorld page about Mertens' third ...
5
votes
1answer
67 views

Minimal Elements with respect to big Oh

Let $\mathcal{F}$ be a finite set of functions from the natural numbers to the natural numbers. Consider the set $S_{\mathcal{F}}=\{g:\mathbb{N}\to\mathbb{N}\mid f\in O(g)\text{ for every } f\in\...
1
vote
1answer
36 views

Closed formula for finite product series

I need to solve the recurrence: $$ \begin{align*} T(n) &= kT\left(\frac{n}{2}\right) + (k - 2)n^3 \\ &\textit{where}\; k \in \mathbb{Z}: k \geq 2 \\ &= k(kT\left(\frac{n}{...
0
votes
0answers
12 views

Recurrence: how to compute the base case when $n$ is its root on each step?

Sorry for maybe vague title, please feel free to change it, if you think you have a better one. I need to solve this recurrence, and this is what I've done so far: $$ \begin{align*} T(n) &= n^...
0
votes
1answer
27 views

Is there a product rule for Big-Omega?

I came upon the need to multiply two function run-times: $\Omega(f)*\Omega(g)$. On wikipedia, such product exists for Big-Oh notation (and equals $O(f*g)$), but the $\Omega$ page is very lacking. I ...
1
vote
1answer
38 views

Proving that $I-EA^{-1} = I+EA^{-1} + o(RelError(\tilde{A},A))$

Let $A\in\mathbb{R}^{n\times n}$ be a non-singular matrix and let $\tilde{A} = A-E$ be an approximation of $A$. The relative error of this approximation is $$RelError(\tilde{A},A) = \frac{\| \tilde{A}-...
0
votes
0answers
16 views

Singular Perturbation Asymptotic Expansion

In the question above, for the outer solution, how do I express the RHS? The question only asks for O(1), but I can express the RHS as (U0 + (U0)^2) * (sum of infinite series of O(1)), where the ...
-2
votes
1answer
30 views

if f and g are monotonically increasing functions, such that f(g(n))=O(n) and f(n)=Ω(n) then g(n)=O(n) [closed]

I have to prove this statement : if $f$ and $g$ are monotonically increasing functions, such that $f(g(n))=O(n)$ and $f(n)=Ω(n)$ then $g(n)=O(n).$
3
votes
0answers
21 views

WKB problem with 4 turning points?

I was recently given a problem that asked to find the solvability conditions for $$\epsilon^2y''=(W(x)-E)y;\quad y\rightarrow0\text{ as }|x|\rightarrow0$$ where $W$ was some piecewise linear, $``W"$-...
0
votes
1answer
23 views

Big Omega and Not Big Omega proofs

I need to proove these three sentences: $g(n) = n + 2n^3-3n^4+4n^5$ $g(n) = \Omega(n^5) $ $g(n) \neq \Theta(5n^6)$ $g(n) = \Omega(nlogn)$ Now, for the Big Omega I have no clue how to do it, for ...
0
votes
1answer
29 views

Asymptotic Inner and Outer Expansion for a Function

In the question above, I understand that to compute the outer layer you take x = O(1). Thus this means in the asymptotic expansion the first term disappears since it is so small. However, there is ...
5
votes
1answer
173 views

Why does the asymptotic expansion of the real-valued Kummer function contain complex terms?

Working on a problem in spectral theory, I need to study the asymptotics of a confluent hypergeometric function (here $(a)_0=1$ and $(a)_s=a(a+1)\cdots(a+s-1)$ denote the Pochhammer symbol) $$ \...
1
vote
0answers
37 views

Relating prime numbers with irreducible polynomials using asymptotic density: is this a known theorem?

Let $p_m$ be the $m$th positive prime number in $\Bbb{Z}$. Then $f \in \Bbb{Z}[X]$ is irreducible if: $$ \liminf\limits_{m \to \infty} \dfrac{\# \{f(n) \text{ is prime } : n \lt p_m \}}{m} \gt 0 $$ ...
-2
votes
1answer
30 views

Need help with question regarding big O [duplicate]

In class we are currently covering upper/lower bounds, big Oh and omega and the like. I am pretty good on the "typical" functions one would do, but at a complete loss at "general" statements. This ons ...
0
votes
0answers
34 views

How to prove or disprove $\forall f\in\mathcal{F}: \lfloor \sqrt{\lfloor f(n)\rfloor }\rfloor \in O(\sqrt{f(n)})$?

If $\mathcal{F}=\{f|f:\mathbb{N}\to\mathbb{R}^+\}$ How to prove or disprove $\forall f\in\mathcal{F}: \lfloor \sqrt{\lfloor f(n)\rfloor }\rfloor \in O(\sqrt{f(n)})$ . So I tried various functions $f:...
1
vote
0answers
24 views

Asymptotic bounds of product of $\log(i)$

$$\prod _{k=2}^n\left(\log_2k\right)$$ Can somebody help me with bounds of this expressions. I see only the rude measure: $$\log_2n\le \prod _{k=2}^n\left(\log_2k\right)\le \left(\log_2n\right)^n$$
0
votes
1answer
14 views

Simple asymptotic analysis problem

I came across a problem that I tried to formalize as follows: Let say i have two functions $x(t)$ and $y(t)$ such that for $t \rightarrow t_0$ $$ \left\{ \begin{array} \;y(t) \rightarrow -\infty \\ ...
0
votes
1answer
32 views

Asymptotic expression for $\left(\frac{1}{\varepsilon}\right)^{\cfrac{1}{1-\varepsilon}}$

My question is regarding the expression below, where $\varepsilon\ll1$. $$\left(\frac{1}{\varepsilon}\right)^{\cfrac{1}{1-\varepsilon}}$$ Is it possible to express this in the form $$\left(\frac{1}{\...
0
votes
0answers
29 views

Need help with a question regarding the Big Oh

In class we are currently covering upper/lower bounds, big Oh and omega and the like. I am pretty good on the "typical" functions one would do, but at a complete loss at "general" statements. This ons ...
0
votes
1answer
28 views

Proving that $2^{2n}-n^2+3^n = \Omega (2^{2n})$

I need to prove that: $2^{2n}-n^2+3^n = \Omega (2^{2n})$ I started and got to this: $2^{2n}-n^2+3^n \geq 2^{2n}\cdot 3 \geq 2^{2n}\cdot 2 = 2^{2n+1}$ for every $n > n_{0} = 1$ How should I ...
1
vote
1answer
20 views

How to prove that $8n^3 + 12n + 3\log^3n \neq \Omega (n^4)$?

How can I prove that $8n^3 + 12n + 3\log^3n \neq \Omega (n^4)$ ? I know that $8n^3 < 8n^4$ , $12n < 12n^4$ and $3\log^3n < 3n^4$ and then I can prove that $8n^3 + 12n + 3\log^3n = O(n^4)$ ...
1
vote
0answers
20 views

Hypergeometric function asymptotics

When calculating the number of possible states of a spin 1 system in a magnetic field, one obtains the following expression $$\#\text{ of states} \propto \,_2 F_1 \left(-\frac{N-P}{2}, - \frac{N-P}{2} ...
0
votes
0answers
34 views

About asymptotic expansion of parabolic cylinder functions

Let's have the parabolic cylinder function $U(a,z)$. I'm interested in its asymptotics for large argument $z$. Here I've found it, but I'm a bit confuzed now because of expressions $(12.9.1)$ and $(12....
2
votes
1answer
57 views

How to show this big O equality.

Let $R(x) = P (x)/Q(x)$ be a rational function with $(\text{degree}\: Q)≥ (\text{degree}\: P )+2$ and $Q(x) \not= 0$ on the real axis. Then I want to prove that $$\int_{-\infty}^{\infty}R(x) e^{-2 \...