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
43 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 } ...
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
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) &= ...
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
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
20 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
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 ...
0
votes
1answer
25 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
168 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
36 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
27 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
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 ...
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
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 ...
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 ...
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
18 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
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 ...
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
59 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
96 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
28 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 ...
0
votes
1answer
58 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
34 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
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) ...
5
votes
2answers
71 views

How is it posible that $f + g \in O(f)$?

I am confused how to do this question. Intuitively it doesn't even make sense how a function $f$ plus another function is in $O(f)$. How can I approach this question: $$ n\log(n^7)+n^{\frac{7}{2}} ...
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
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 ...
0
votes
1answer
35 views

On “bounded” in intuition for a 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 ...
1
vote
0answers
39 views

Help on Big O proof

I need some help with a big O proof. I think I have a proof but I feel like some of the steps aren't logically compatible. The Question: For all functions f,g with domain $\mathbb{N}$ that maps to ...
1
vote
1answer
47 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 ...
0
votes
0answers
32 views

Asymptotic to $f^{-1}(f ' (x)) $?

Let $tr(n)$ be the triangular numbers and $te(n)$ be the tetrahedral numbers. $$g(x) := \sum \frac{x^n}{n! 2^{tr(n)}}$$ $g'(x) = g(\frac{x}{2}) $ Now consider the analogue $$ f(x) = \sum ...
0
votes
1answer
21 views

Lower bound on binomial coefficient

Prove that $\binom{n}{k} ≥ \left(\frac{n}{k}\right)^k$ for integers $0<k<n $. I used Stirling formula to find the the combination of the left part but it goes very long and I can not find and ...
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 ...
1
vote
1answer
48 views

Has limit $\frac{\sigma_0(n)\sigma_2(n)}{(\sigma(n))^2H_n},$ where $H_n$ is the nth harmonic number?

By specialization of an inequality I can write $$2 \sum_{k=1}^{n-1} \frac{1}{d_{k}} \sum_{l=k+1}^{n} \frac{1}{d_{l}}\leq 2\frac{\sigma_0(n)-1}{\sigma_0(n)}\cdot \left( \frac{\sigma(n)}{n} \right)^2, ...
0
votes
1answer
20 views

How to calculate $O(\sum_{k=1}^{K}(N-k)(k+1)^2)$?

Using the formula for the sum of the squares and the sum of first $K$ numbers I can get that: $$\sum_{k=1}^{K}(N-k)(k+1)^2=\dfrac{1}{12}K(-3K^2+2K^2(2N-7)+3K(6N-7)+26N-10)$$ Now I guess I can ...
1
vote
2answers
28 views

Big-O proof of inclusion

I'm working on this proof of inclusion:$$\log_2(8^n)\in{\mathcal O(n)}$$ $$\log_28^n-cn\leq0$$ for all $n>n_0$. Is there a log rule that I can use to further simplify before I plug random values to ...
0
votes
0answers
18 views

asymptotic expansion of an expression involving modified bessel function

I am looking for the asymptotic behavior of $$g(t,\nu)=e^{-t^2}\left[I_\nu(t^2)+\frac{1}{2}\left(I_{\nu+1}(t^2)+I_{\nu-1}(t^2)\right)\right]$$ as $t\rightarrow \infty$. Here $\nu$ only takes even ...
3
votes
0answers
101 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 & ...
2
votes
2answers
60 views

Arrange the following:$(1.5)^n, n^{100}, (\log n)^3, \sqrt n\log n, 10^n, (n!)^2, n^{99}+n^{98}, 101^{16}$

Here is the question repeated: Arrange the following in order into increasing order of growth rates. $$(1.5)^n, n^{100}, (\log n)^3, \sqrt n\log n, 10^n, (n!)^2, n^{99}+n^{98}, 101^{16}$$ I graphed ...
1
vote
0answers
46 views

Complexity of FFT algorithms (Cooley-Tukey, Bluestein, Prime-factor)

I need to be able to explain the complexity of three Fast Fourier Transform algorithms: Cooley-Tukey's, Bluestein's and Prime-factor algorithm. Unfortunatelly, I'm a little lost in the process. ...