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

learn more… | top users | synonyms (1)

3
votes
1answer
39 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} ...
3
votes
0answers
70 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
5answers
125 views

Which function grows at a faster rate? $n!$ or $2^{n^2}$

I have two functions: $n!$ $2^{n^{2}}$ What is the difference between the growth of these two? My thought is that $2^{n^2}$ grows much faster than $n!$.
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?
0
votes
0answers
22 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
38 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.: ...
0
votes
0answers
47 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
1answer
29 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
votes
1answer
22 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 ...
1
vote
0answers
60 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
26 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
15 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 ?
0
votes
0answers
25 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 ...
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 \\ ...
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 } ...
2
votes
0answers
107 views

$f(x)\sim 1/x \implies (1+f(x))^x\to e$, but what family of functions maximizes the speed of convergence from below?

This problem is subordinate to finding out if $$\left(1+\frac{\log p_{n+1}}{p_n}\right)^{p_{n+1}/\log p_n},$$where $p_n$ is the $n$-th prime, never stabilizes above or below its limiting value, which ...
1
vote
1answer
29 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 \\ &= ...
0
votes
1answer
25 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
37 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{\| ...
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) &= ...
-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).$
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 ...
3
votes
0answers
18 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, ...
0
votes
1answer
24 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 ...
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 ...
3
votes
0answers
100 views

$2\times 2$ block Toeplitz determinant

My question is about computing asymptotic the determinant (dimension of the matrix $n\to\infty$) of a $2\times 2$ block Toeplitz matrix. $$\mbox{det}\left(\begin{array}{cc} a_n & b_n \\ d_n & ...
1
vote
0answers
35 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 $$ ...
1
vote
1answer
102 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) ...
1
vote
1answer
27 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 ...
-2
votes
1answer
26 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
1answer
47 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
0answers
22 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
0answers
33 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 ...
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 ...
0
votes
0answers
28 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 ...
4
votes
1answer
57 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
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)$ ...
0
votes
0answers
28 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 ...
1
vote
0answers
17 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
4answers
95 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)$?
3
votes
0answers
33 views

Asymptotic bounds on the number of faces needed to construct a polyhedron of a certain genus

Let a polyhedron be a solid in three dimensions with flat polygonal faces, straight edges and sharp corners or vertices, where moreover we require that every edge touches exactly two faces, every ...
0
votes
0answers
26 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
37 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 ...
3
votes
1answer
51 views

Deriving Stirling's approximation formula via the definition of the Gamma function

In my asymptotic analysis and combinatorics class I was asked this question: We first remember the definition f the Gamma function $ \Gamma(n+1) = n! = \int_{0}^{\infty} t^{n} e^{-t} dt $ and ...
1
vote
2answers
30 views

Expectation of a transformed random variable

I'm trying to prove the following: Let $X_n$ be a sequence of positive random variables and $g$ be a positive function. Suppose that $E[X_n]\to \infty$ as $n\to\infty$. If $E[g(X_n)]$ exists, there ...
0
votes
1answer
32 views

Troubles proving $O[f(n)] \cdot O[g(n)] = O[f(n) \cdot g(n)]$

Prove that $O[f(n)] \cdot O[g(n)] = O[f(n) \cdot g(n)]$, knowing that $O[g(n)] = \left\{ f(n) \mid \exists\ c,n_0 > 0\ :\ 0 \leq f(n) \leq c \cdot g(n)\ \forall\ n \geq n_0 \right\}$ I don't ...
0
votes
1answer
33 views

Correctness of Idea of Big O Proof

I have this big O proof and was wondering about the correctness of my rough work. Could anyone confirm if my idea for my proof is correct? Here is the question: Let ...
1
vote
1answer
45 views

On corollary and theorem involving autonomous 1st-order ODEs

Suppose we have an autonomous first-order ordinary differential equation $$\frac{dx}{dt} = f(x) \tag{*}$$ where $f$ is continuously differentiable for all $x \in D \subseteq \mathbb R$ s.t. the ODE ...