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
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
28 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
26 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
35 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
26 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 \...
4
votes
1answer
63 views

Boundary layers: approximately satisfying BC

I am working on a boundary layer problem for a second order linear ODE. A simpler problem which I think still illustrates the issue I am having is $$\varepsilon y''-y'+y=0,y(0)=0,y(1)=1$$ where $\...
0
votes
4answers
97 views

Prove $\log(n!) =\Omega(n\log(n))$ [closed]

Can someone help me prove that $\log(n!) =\Omega(n\log(n))$, that is, that there exists some positive $c$ such that, for every $n$ large enough, $\log (n!)\geqslant c\cdot n\cdot \log(n)$?
0
votes
0answers
31 views

Help with basic arithmetic involving Big Oh

I'm trying to determine the resulting "Big Oh" when arithmetic operators are applied between two different functions, but I'm a bit unsure after looking at even the basic operators shown on wikipedia ...
1
vote
1answer
38 views

Patterns in the plots of $\ln |\sin N|$ and $\ln | \cos N|$ for large integer $N$

Since no integer $N$ is a rational multiple of $\pi$ it's obvious that $\sin N$ and $\cos N$ will not give any 'nice' values for any $N$. Actually, I thought the values would get essentially random ...
0
votes
1answer
59 views

What is the pattern of the Stirling series?

It can be shown that: \begin{eqnarray*} n! = \left ( \frac{n}{e} \right )^n \sqrt{2 \pi n} e^{ \frac{B_2}{2n} + \frac{B_4}{4 \cdot 3 \cdot n^3} + \cdots + \frac{B_{2m}}{2 m ( 2m-1) ...
1
vote
1answer
44 views

Proof involving Big O and floor

Trying to prove or disprove this (pretty sure it's correct): Let $\mathcal{F}=\{f\mid f:\mathbb{N}\to\mathbb{R}^+\}$ $$\forall f\in\mathcal{F}: \left\lfloor \sqrt{\lfloor f(n)\rfloor }\right\rfloor \...
1
vote
1answer
104 views

Prove that if $\log{f(n)} \in O(g(n))$ then $f(n)\in O(3^{g(n)})$

Let $\mathcal{F}=\{f|f:\mathbb{N}\to\mathbb{R}^+\}$ $$\forall f\in\mathcal{F}: \log{f(n)} \in O(g(n))\implies f(n)\in O(3^{g(n)}).$$ How to prove this? I thought about first showing that $$g(n) \...