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

Rate of convergence of an exponential function

If I have a function $$f = \exp(\sqrt{n} \cdot \frac{\sqrt{\log{n}}}{\sqrt{n}-\sqrt{\log n}}),$$ I can notice, that $$\lim_{n \to \infty} f = \infty,$$ but also I can notice that it goes very slowly ...
3
votes
1answer
48 views

Prove $\lim_{n \to \infty} \frac{\Gamma(n+1/2)}{\Gamma(n)~n^{1/2}}=1$

Prove $$\lim_{x \to \infty} \frac{\Gamma(x+1/2)}{\Gamma(x)~x^{1/2}}=1.$$ I got this problem from Probability and Statistics by Degroot & Schervish. There is a hint to use Stirling's formula ...
1
vote
1answer
33 views

Uniform asymptotic expansion

Let the function $f(x,\nu)$, with $x>0$ and $\nu\in[0,+\infty)$, have the asymptotic expansion \begin{equation} f(x,\nu)\sim\sum_{n=0}^{\infty}a_{n}(\nu)x^{n}\;, \end{equation} as $x\to 0$. Assume ...
0
votes
0answers
22 views

Differential equation question to do with modelling gravity.

Hi I am given two models for the gravity of earth, the first is with $x_3$ normal to the earth and is $m\ddot{x}(t)=-mg(0,0,1)^T$ the other is with $x$ a distance vector from the centre of the ...
0
votes
0answers
61 views

OEIS sequence A086449

OEIS sequence A086449 http://oeis.org/A086449 is defined by: $a(0)=1$, $a(2n+1)=a(n)$, $a(2n) = a(n)+a(n-1)+\ldots+a(n-2^m)+\ldots$ $= a(n)+\sum_{i=0}^{\lfloor\lg n\rfloor}a(n-2^i)$ One can show ...
3
votes
3answers
88 views

Asymptotic expansions for the roots of $\epsilon^2x^4-\epsilon x^3-2x^2+2=0$

I'm trying to compute the asymptotic expansion for each of the four roots to the following equation, as $\epsilon \rightarrow 0$: $\epsilon^2x^4-\epsilon x^3-2x^2+2=0$ I'd like my expansions to go ...
1
vote
1answer
48 views

Integer Partition into Powers

Is there any way to count the number of integer partitions of a number N into powers of two such that each size is repeated a power of two times? Ok so the recurrence can be expressed by: $a(0)=1$, ...
5
votes
0answers
176 views

Summation of $1/(xy)$ over a triangular region

Let us consider a lattice formed by all points with integer and positive coordinates on a Cartesian plane, and where $K$ is the maximal value for the x-axis. Let us assign to each lattice point the ...
1
vote
1answer
47 views

Need help in finding the asymptotic variance of an estimator.

I kinda doing some review questions for my finals and I kinda got stuck on this question. I'm able to do part a by finding the maximum likelihood estimator but for some reason. To find the ...
0
votes
0answers
43 views

How to get the asymptotic formula of generalized Bessel function?

How to get the asymptotic formula of generalized Bessel function? $$J_{\nu}^{(\mu)}(z)=\frac{2}{\sqrt{\pi}\Gamma(\nu+1-1/\mu)}\Big(\frac{z}{2}\Big)^{\mu \nu/2} \int_{0}^{1} ...
0
votes
2answers
61 views

Is $x^2+25x+4 \in \mathcal{O}(x^2)$? If yes how? If no why not? [closed]

Is $x^2+25x+4 \in \mathcal{O}(x^2)$ ? if yes how ?, if no why? i know x^2+25x+4≤25x^2+25x+25≤25x^2+25x^2+25x^2=75x2 for some x what confuses me is x^2+25x+4≤25x^3+25x+25≤25x^3+25x^3+25x^3=75x3 ...
2
votes
1answer
43 views

Leading order approximation to differential equation

Find a leading order approximation to the solution of $\epsilon y'' + 2 y' + e^y = 0$, $y(0)=y(1)=0$ as $\epsilon \to 0$. I know there is a boundary layer near $x=0$ and not at $x=1$ so I can ...
1
vote
0answers
43 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 ...
0
votes
1answer
37 views

Using arithmetic progression sum to show an algorithm is both $\Theta(n^2)$ and $O(n^2)$

Exercise 4 in http://discrete.gr/complexity/ askes to give an arithmetic progression sum to show that the following algorithm is both $O(n^2)$ and $\Theta(n^2)$. ...
3
votes
1answer
47 views

Asymptotic approximation to find the Barnes integral

In the following paper and in order to prove the Barnes integral $$\frac{1}{2\pi ...
2
votes
1answer
51 views

What is the order of the product of $ \frac{p-1}{p} $ under the square root of a prime?

Is there any known asymptotical order for $$ \prod_{p_k\ \text{prime}}^{\sqrt{p_n}} \frac{p_k-1}{p_k} $$
1
vote
2answers
65 views

Asymptotics of logarithms of functions

If I know that $\lim\limits_{x\to \infty} \dfrac{f(x)}{g(x)}=1$, does it follow that $\lim\limits_{x\to\infty} \dfrac{\log f(x)}{\log g(x)}=1$ as well? I see that this definitely doesn't hold for ...
3
votes
1answer
29 views

Asymptotic analysis of an integral with growing, highly oscillatory integrand

I recently came across the following integral $$\int_0^{\omega} t^{\frac{n-1}{2}}|\cos(t^n)|\,dt.$$ Here $n>1$ is an integer. I was curious as to what its asymptotic form would be. It seems to be ...
2
votes
1answer
30 views

Estimating sum of n elements by throwing away half of elements

I've got a task where i need to proove the asymptotic big-Theta equation: $$ \log n! = \Theta(n \, \log n) $$ $ \ $ Since $f(\mathit{n}) \in \Theta(g(\mathit{n}))$ means that $g(n)\cdot k{_1} \leq ...
5
votes
3answers
122 views

Proof that $J_{\nu}(x) \sim (x/2)^\nu / \Gamma(\nu+1) \; \text{as} \; \nu \rightarrow \infty$

I'm working through the exercises of Bender and Orszag's famous book, but I got stuck in 6.25 (a), in which it is asked to prove that $$J_\nu (x) \sim (x/2)^\nu / \Gamma(\nu+1) \; \text{as} \; \nu ...
12
votes
2answers
161 views

Convergence of power towers

Let's define the sequence $\{s_n\}$ recursively as $$s_1=\sqrt2,\ \ \ s_{n+1}=\sqrt2^{\,s_n}.$$ Or, in other words, $$s_n=\underbrace{\sqrt2^{\sqrt2^{\ .^{\ .^{\ .^{\sqrt2}}}}}}_{n\ \text{levels}}.$$ ...
2
votes
0answers
24 views

Prove or disprove the Big-O of an exponential function

$f(n) = 2^{n+1} = O(2^n)$ Intuitively, I think the statement is false. However, when I go about disproving it, I find that $2^{n+1} = 2^n \cdot 2$, meaning that if there is a constant $C$ larger than ...
0
votes
0answers
17 views

Big-Oh for size of a Sperner family

I'm developing an algorithm that will generate a collection of subsets of a ground set having the property that no subset in the collection is a subset of any other, and I'd like to give a Big-Oh ...
1
vote
0answers
123 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 ...
0
votes
0answers
40 views

Symbol of self-adjoint pseudodifferential operator

It seems that the following result should hold, but I can't find it explicitly anywhere. If $A=A^*$ is a properly supported pseudodifferential operator, does this imply that ...
1
vote
1answer
20 views

asymptotic behaviour of a product

Suppose $a_j\downarrow 0,b_j\downarrow 0$, and $a_j/b_j\rightarrow 1$. Do we always have $\prod_{j=1}^n\frac{1-a_j}{1-b_j}\rightarrow c$ as $n\rightarrow\infty$ for some finite constant $c$? Thanks!
0
votes
1answer
31 views

Asymptotic behaviour of a couple of special functions (features exponentials and logarithms)

I'm dealing with a couple of functions: $n \log n$, $( \log \log n)^{ \log n}$, $( \log n)^{ \log \log n}$, $n e^{\sqrt{n}}$, $( \log n)^{ \log n}$, $n 2^{ \log \log n}$, $n^{1+1/( \log \log ...
4
votes
1answer
50 views

On the sum of relatively prime number $<N$

Let $A(N)$ be a function which is the sum of all numbers relatively prime and $<N$ and $B(N)$ the sum of remaining $N−\phi(N)$ numbers. Then I have the following questions- Q-1 For what values of ...
1
vote
0answers
48 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 ...
5
votes
0answers
101 views

Asymptotic expansion of $\zeta(s)$

It is well known that $$ \zeta(s) = \sum_{n = 1}^\infty \frac{1}{n^s} = \prod_{p \text{ prime}} \frac{1}{1 - p^{-s}}, \quad \Re[s] > 1, \tag{1}$$ but, if $p \leq N$ denotes the primes less than or ...
-2
votes
1answer
47 views

Prove that $\log n = O(\log^2 n)$

Trying to solve this, but I can't seem to figure it out. Its fairly straight forward.
1
vote
1answer
37 views

Rearranging asymptotic notation

If $a \le b^{\frac{1+\log_{2}b}{2}}(1+o(1))$, then what is $b$ in terms of $a$? Whenever I try to rearrange this, I get in a huge mess... Any help would be appreciated. Thanks.
2
votes
2answers
75 views

How to find the asymptotic behavior of this function

I have a function that I want to study it's asymptotic behavior. The function is $$ f(k) = - \frac{k^2}{4} - \frac{\log\pi}{2} + \log\left( \frac12 \left| \mathrm{Erfi}(\frac{k}{2} - \pi i) - ...
2
votes
2answers
52 views

Asymptotic approximation of binomial theorem

Binomial theorem is a very popular theorem that: $$(x + y) ^ n = \sum_{i=0}^n {n \choose i}x^i y^{n-i}$$ I am looking for any papers (the newer the better) where I can find any informations about ...
0
votes
1answer
17 views

Asymptotics of a bounded function

We have given a function $f(x)$ where we know that $f(x)\leq 1$ for all $x$. Is it true that $$1+O(f(x))=O(f(x))$$ even though I know that $1 \geq f(x)$? We know that $O(f(x))=o(g(x))$. Is it true ...
2
votes
1answer
44 views

Prove or disprove a big o statement

I have to prove or disprove the following statement: $\forall a,b \in \mathbb{R}$, $b > 1$ : $n^a \in O(b^n)$ Clearly there are 2 cases: (i) $a < 0$ and (ii) $a \geq 0$, meaning that I have ...
1
vote
0answers
34 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
0
votes
1answer
43 views

Expected number of $k$-cliques in $G(n, 1/2) \ge 1$

Let the expected number of $k$-cliques be denoted by $$f(k) = \binom{n}{k} (\frac{1}{2})^{- \binom{k}{2}}$$ let $k_0$ denote the largest $k$ such that $f(k) \ge 1$. I want to prove that $k_0 = ...
1
vote
1answer
41 views

Which one of the following is greater?

Hi I am studying Asymptotic analysis but generally find difficulty in identifying the greater of two functions ? Like ex. $$f(n) = ((n^2)(\log_2(n))\\ g(n) = n((\log_2(n))^{10})$$ (here log are to ...
7
votes
6answers
899 views

Which one is bigger $2^{n!}$ or $(2^{n})!$?

Which one is bigger $2^{n!}$ or $(2^{n})!$ ? where $n\in\mathbb N$.
4
votes
0answers
60 views

Looking for a closed form for the quotient of a sequence of compositions of $\exp()$-function

Related to that previous question I have another still open detail problem. Consider the sequence of evaluations at some given $x$ $$ \small \begin{array} {} z_0 &=& e^x \\ z_1 ...
11
votes
1answer
96 views

Expected values of some properties of the convex hull of a random set of points

$N$ points are selected in a uniformly distributed random way in a disk of the unit radius. Let $P(N)$ and $A(N)$ denote the expected perimeter and the expected area of their convex hull. For what ...
2
votes
2answers
49 views

Master theorem - why the log factor?

I think I finally managed to fully understand the master theorem but there's one thing left in the second clause (I'm following here: ...
0
votes
0answers
16 views

Can someone help me solve this recurrence using the Master Theorem?

Can someone help me solve this recurrence? $$T(n)= T(n^{1/2}) + Θ(\log\log n)$$ I know that I have to change the variables $m=\log n$. Then I have: $$S(m)=S(m/2)+Θ(\log m)$$ Case 2 of Master ...
1
vote
1answer
75 views

Order related to Empirical distribution function and Normal distribution

Let $X_1,\dots,X_n$ are i.i.d with distribution function $F$. Let $\hat F_n$ be its empirical distribution function, i.e., $$ \hat F_n(x)=\frac1n\sum_{i=1}^n1_{\{X_\le x\}}(x) $$ where $1_A(x)$ is the ...
4
votes
3answers
230 views

Asymptotic expansion of $J(t) = \int^{\infty}_{0}{\exp(-t(x + 4/(x+1)))}\, dx$

I want to derive an asymptotic expansion for the following Bessel function. I think I need to rewrite it in another form, from which I can integrate it by parts. I am interested in obtaining the ...
4
votes
1answer
44 views

Problem understanding Master theorem

I'm studying the Master theorem (for the analysis of recursive algorithms) and I perfectly understand why a binary search is of order $\log_2(n)$. I also understand that if we formulate it as $T(n) ≤ ...
5
votes
0answers
94 views

What's the most efficient way to mow a lawn?

For $S\subseteq\Bbb R^2$ and $x\in\Bbb R$, define $E_x(S)=\{y\in\Bbb R^2:d(y,S)<x\}$. ($E_x(S)$ represents the expansion of $S$ by $x$.) Given a path $\gamma:[0,1]\to\Bbb R^2$, denote its length as ...
-2
votes
1answer
23 views

Simple question about big O

If $f(n)=g(n)$, can we just say that $\mathcal{O}(f(n))=\mathcal{O}(g(n))$? ($f$ and $g$ are two $\log$ functions) Is it definitely yes? if not please describe why.
0
votes
0answers
44 views

Iterative Logarithm

For the iterative logarithm log log* n prove that it is a function of o(logk n) but also ω(1). For ω(1). I can prove that the function is ω(1) if I can show that log* n -> ...