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

learn more… | top users | synonyms (1)

2
votes
0answers
60 views

gamma funtion and estimates-typo or mistake?

In one of the lecture notes I've found that $C_n$ $$ C_n= \begin{cases} \frac{n!}{\sqrt 2 \Gamma((n/2+1)}\pi^{-1/42^{-n/2}(n!)^{-1/2}} & n\text{ even} \\[4mm] \frac{2(n!)}{(\sqrt2n+1/(\sqrt2 ...
2
votes
0answers
69 views

On bounding the average cost of top-down merge sort

Let $A_n$ be the average number of comparisons to sort $n$ keys by merging them in a top-down fashion (see any algorithm textbook). It can he shown that $$ A_0 = A_1 = 0;\quad A_n = ...
2
votes
0answers
48 views

Local polynomial fitting using Taylor expansion

My question is about the usage of Taylor expansions when dealing with asymptotics in local polynomial fitting. The expressions that set me of are of the type: $$ g(X_i) = \sum_{j=0}^{p} ...
2
votes
0answers
204 views

Asymptotic bounds for a sum

I have this sum, which probably doesn't exist in closed form. $$\displaystyle ...
2
votes
0answers
186 views

Upper bound for the quality of an $abc$-triple

A triple of positive integers $(a,b,c)$ is an $abc$-triple if $a$ and $b$ are coprime and $c = a + b$. Define the quality or power of an $abc$-triple as $P(a,b,c) = \frac{\log c}{\log ...
1
vote
0answers
10 views

Asymptotic Notations Iterative Method for Solving Recurrences

Recurrence T(n)= T(n^1\2) + O(lg(lg(n))) The solution suggests substituting m = lg(n) So the recurrence becomes S(m)= S(m\2) + O(lg(lg(m))) Then solving using iterative method for solvng ...
1
vote
0answers
8 views

Strategies for approximating fourier transform of $k$-th power of the $n$-th derivative of a function

For a function $f(x)$ with Fourier transform $\hat{F}(q)$, I'm interested in understanding the relationship of the Fourier transform of a power of a derivative of $f$ to $\hat{F}(q)$. Explicitly, I ...
1
vote
0answers
32 views

Approximate solutions for quintic equation

The other day I asked a question in here about deriving the equations $$u^2\left(\left(1-s_1\right)+3u+3u^2+u^3\right) =\alpha\left(s_0+2s_0u+\left(1+s_0-s_1\right)u^2+2u^3+u^4\right),$$ where ...
1
vote
0answers
25 views

Mutual Asymptotic analysis of the given fucntions

$ f(n)$ = $ 3n^{\sqrt{n}} $ $g(n)$ = $2^{\sqrt{n}log_2n}$ $h(n)=n! $ For all the $3$ pairs of the functions, which one is $Big-O$ of which ? I am unable to compare these functions. Edit : I ...
1
vote
0answers
26 views

Asymptotic behavior of the solution of a 2nd order linear ordinary differential equation

In studying the harmonic oscillator, we encounter the equation $$ f'' +(2E - x^2) f = 0$$ What is the asymptotic behaviour of the solution to this equation for a generic $E$? Any good book on ...
1
vote
0answers
33 views

Heat equation, boundary gradient singularity

Consider the Cauchy-Dirichlet problem for the heat equation in a non-cylindrical region $\Omega \subset \mathbf{R}^+ \times \mathbf{R}$: $\Omega = \{ (t,x): \; 0 \leq t \leq 1, \; x \leq ...
1
vote
0answers
46 views

$\epsilon y''+\sqrt{x}y'+y=0$, show there is no boundary layer at $x=1$ and a boundary layer of $\epsilon^{\frac{2}{3}}$ at $x=0$?

I'm so lost. If I use quadratic formula I obtain that: $$y(x) = ae^{-2\epsilon\sqrt{x}}+be^{-2x\sqrt{x}+2\epsilon\sqrt{x}}$$ with the boundary conditions $y(0)=0$ and $y(1)=1$ but how does this lead ...
1
vote
0answers
11 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 ...
1
vote
0answers
21 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 ...
1
vote
0answers
34 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 ...
1
vote
0answers
24 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 ...
1
vote
0answers
31 views

Asymptotic expansion of $(\text{log}(1+x))^2$

How can I find asymptotic expansion of the function $(\text{log}(1+z))^2$ with respect to the asymptotic scale $\{z^{-m}, z^{-n}\text{log}(z), z^{-p}\text{log}^2(z), m,n,p=0,1,2,...\}$ while ...
1
vote
0answers
30 views

What does “combining the solutions in O(n) time” mean?

Algorithm $X$ proceeds by recursively solving $5$ subproblems of one-half the size, then combining the solutions in $O(n\log n)$ time. Algorithm $Y$ makes $9$ recursively calls on ...
1
vote
0answers
28 views

Help with understanding how to sketch a graph of y=1/f(x) and y = xf(x)

I'm having problems trying to figure out how to sketch a graph for these 2 questions. Could someone provide me a step by step guide on how to do this? Thanks in advance.
1
vote
0answers
29 views

BusyBeaver growth: “simple” proof

I just try to prove that $BB(n)$ (BusyBeaver-Function) grows faster than any other computable function. Maybe someone can check the proof? $f(n)$ is a computable function which grows to infinity: ...
1
vote
0answers
59 views

Big-O estimate (smallest order)

I'm trying to give a big-O estimate for each of these functions, where I want to use a simple function $g$ of smallest order. I have them all done I just wanted to someone to run through and check ...
1
vote
0answers
50 views

Asymptotics of expectation of a ratio of binomially distributed random variables

Let $X_n \sim Bin(n_1,p_1)$ and $Y_n \sim Bin(n_2, p_2)$ with $n_1 + n_2 = n$ and $p_1,p_2 >0$ be independent, binomially distributed random variables. We furthermore assume that $\frac{n_1}{n} \to ...
1
vote
0answers
28 views

Asymptotic behaviour of $\varphi''(x)=F(\varphi(x))$

I'm concerned with the discussion of a ODE, especially the discussion of the solution. I've got the assumptions that there is the relation $\varphi''(x)=F(\varphi(x))$ for all $x$ on $\mathbb{R}$. ...
1
vote
0answers
54 views

sum over primes involving divisor function (variation of the Titchmarsh divisor problem)

Does there exist an asymptotic estimate for the following sum over primes $$ \sum_{p\leq x} \frac{\tau(p-1)}{p}\;, $$ where $\tau(n)=\sum_{d|n}1$ is the divisor function?
1
vote
0answers
68 views

Using Limits to Determine Big-O, Big-Omega, and Big-Theta

I am trying to get a concrete answer on using limits to determine if two functions, $f(n)$ and $g(n)$, are Big-$O$, Big-$\Omega$, or Big-$\Theta$. I have looked at my book, my lecture notes, and have ...
1
vote
0answers
14 views

Recursive relation-Theta notation

Consider the recursive relation: $$T(n)=T(an)+T((1-a)n)+cn$$ where $0<a<1$ and $c>0$ are constants(independent of $n$).Show that $T(n)=\Theta(n \lg n)$ That's what I have tried: We ...
1
vote
0answers
73 views

Find a closed form for the constant term

In a previous question, an asymptotic expansion was provided for the weighted divisor summatory function $\displaystyle \frac {d(n)}{n}$: $$\sum_{n\leq ...
1
vote
0answers
19 views

Showing that $\prod_i{\frac{qi-1}{qi}}=\exp(-\frac{\log n- \log q +O(1)}{q})$

I'm currently making my way through Dixon's paper 'The Probability of Generating the Symmetric Group'. (It can be found here.) In the proof of lemma 3 it is asserted that ...
1
vote
0answers
38 views

Asymptotic behaviour / Convergence

Let $0<\omega<\infty, \mu >0$ and $z \in \mathbb{R}.$ In my book, it is written that we have the following asymptotic behaviour: i) Claim: $$\lim_{t \rightarrow \infty} \frac{z ...
1
vote
0answers
33 views

How to show an aymptotic expansion is uniformly valid?

I have an equation $$ nt = u - \epsilon \sin(u) $$ which asks for the first four terms in the asymptotic solution. Hence if the solution is $u_0 + \epsilon u_1 + \cdots.$, expand $\sin(u)$ around ...
1
vote
0answers
57 views

Definition of $O (.) $ notation

The book I am currently reading defined the big oh operator as the following: A function $ g (x) $ said to be $ O (h (x)) $ as $ x \to l $ if $\lim \sup_{x \to l} |g (x)/h (x)| < \infty $. What I ...
1
vote
0answers
47 views

What is the sign of the generalized Stieltjes constants $\gamma_{k}(a)$?

Recall that the Stieltjes constants $\gamma_{k}$ appear as the coefficients in the regular part of the Laurent expansion of the Riemann zeta function about $s = 1$: $$ \begin{align} \zeta(s) = ...
1
vote
0answers
30 views

Asymptotic behavior of sums of consecutive powers (bivariate)

Are there some (bivariate) closed form formulas for the asymptotic behaviour of the sum: $$\sum_{k=1}^{n} k^d,$$ where $n$ and $d$ are large integers? I am especially interested in a lower bound of ...
1
vote
0answers
43 views

Approximations for finite n in limit-based definition of the exponential function

The exponential function can be defined via: $$ e^x = \lim_{n \rightarrow \infty} \left( 1 + \frac{x}{n} \right)^{n} = \lim_{n \rightarrow \infty} g(x; n) $$ In my problem, I actually have the right ...
1
vote
0answers
33 views

Question about finite sums and integer recursions.

Let $n$ be a positive integer and let $g(n)$ be a given strictly increasing integer function such that $0<g(n)<n$ for all $n$. Also the sequence $ |g(n) - n|$ is unbounded as $n$ grows. Let ...
1
vote
0answers
64 views

Long-time asymptotic behaviour of a system of two ODEs

We have the following nonlinear ODE: $$ f' = af-bg -(f+g)^k \bigl(f'(0) +g'(0)\bigr) + f'(0), $$ $$ \bigl(G-T(x)\bigr) g' = -af+bg - g'(0), $$ where $a,b,k,G$ are constants, $f'(0)$ and $g'(0)$ are ...
1
vote
0answers
32 views

What is the power series for a half-exponential function?

What is the power series of a half-exponential function? Half-exponential means that $f(f(x)) = y^x, y > 1$
1
vote
0answers
31 views

How can I show that the solution of the recursive realtion is $O(n \lg n)$?

Show that the solution of the recursive relation $T(n)=2T( \lfloor \frac{n}{2} \rfloor +17)+n$ is $O(n \lg{n})$. I am supposed to use the substitution method.. That's what I have tried: Let ...
1
vote
0answers
25 views

Asymptotic behavior of oscillatory Hilbert transform

Does anyone know what is the leading term in the asymptotics of $$ P.V. \int\limits_{ -\infty }^{ +\infty } \frac{e^{i \lambda x^3 } f( x ) dx }{ x }, $$ as $ \lambda \to +\infty $? Assume $ f \in ...
1
vote
0answers
52 views

Sums of Power Law random variables

Suppose $F$ be a pareto distribution with scale parameter $x_m$ and shape parameter $\alpha$. Assume $X_1, X_2 , ..., X_n$ are iid random variables drawn from $F$. Let $S_n(k) = X_1 ^k + X_2 ^k + ...
1
vote
0answers
25 views

asymptotics of the solution of an integral equation

Suppose we are given the integral equation $$ u(x;a) =v(x)+\int_0^a K(x,y)\,u(y;a)\,dy, $$ where $K(x,y)$ and $v(x)$ are known functions, and $a>0$ is a constant. What I am interested in is the ...
1
vote
0answers
88 views

Does the index of a curve determine the asymptotic behaviour of certain vector fields?

There are a collection $C$ of charges in $\mathbb{R}^2$ which cause an electric vector field $V$ to form. Each charge's contribution to $V$ follows the inverse-square law. Let $\gamma$ be a curve ...
1
vote
0answers
53 views

Integration vs Summation

I am interested in how one might generally evaluate, or estimate $$G(x)=\sum_{n=1}^{\infty}f(n)x^n-\int_{0}^{\infty}f(t)x^tdt$$ as $x\to1^-$, and for a continuous $f$, and such that the integral ...
1
vote
0answers
65 views

Prime Zeta Function

Does $$\sum_{p \text{ prime}} \frac{1}{p^s} \sim \log \zeta(s) \quad \text{as} \quad s \to 1^+$$ imply $$\sum_{p \leq n} \frac{1}{p} \sim \log H_n \quad \text{as} \quad n \to \infty,$$ where $H_n$ is ...
1
vote
0answers
125 views

Limit of sequence of integral related i.i.d. observations

Let $X_1,\dots,X_n$ be i.i.d. random variables, each uniformly distributed on $[0,1]$. Let $\hat F_n$ be their modified empirical distribution function, i.e., $$ \hat ...
1
vote
0answers
35 views

Simplify $\frac{n(k^2-1)}{2}$ to $ nk^2$

How does $\frac{n(k^2-1)}{2}$ become $nk^2$? I'm sorry for the stupid question but I'm at wits end and I have no idea how to go about this. Context Thanks
1
vote
0answers
58 views

Evaluating a Limit with Generalized Harmonic Numbers.

Using WolframAlpha, I could informally come up with the following result: $$ \lim_{n \rightarrow \infty} \frac{H_n^{(-\frac{1}{2})}}{n\sqrt{n}} = \frac{2}{3} $$ Allowing me to infer that ...
1
vote
0answers
118 views

Big-O Notation for remainder terms in Taylor expansion

The Big-O notation is commonly used in Taylor expansions of the form $$f(x+\epsilon)=f(x)+\epsilon f'(x)+O(\epsilon^2)$$ to say that the remainder term grows at least quadratic around $\epsilon=0$. ...
1
vote
0answers
55 views

Integral asymptotics

Is there some kind of a variation of the Laplace's method or some other formula for the asymptotics of integrals of a type $$\int_a^bf(x)e^{mp(x)}\cos(mq(x)+x/2)dx, \ m\to\infty.$$ Here $f,p,q$ are ...
1
vote
0answers
51 views

Is $\log^* (n+1)^{n+2} \in O(\log^* n)$?

I would like to know if $\log^* (n+1)^{n+2} \in O(\log^* n)$, where $\log^*$ is the iterated logarithm. I tried doing: $ \log^* (n+1)^{n+2} =\\ \log^{*}(\log(n+1)^{n+2})-1 =\\ \log^{*}((n+2) \cdot ...