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

learn more… | top users | synonyms (1)

0
votes
0answers
8 views

Runtime Complexity | Recursive calculation using Master's Theorem

So I've encountered a case where I have 2 recursive calls - rather than one. I do know how to solve for one recursive call, but in this case I'm not sure whether I'm right or wrong. I have the ...
1
vote
1answer
11 views

Find upper bound time complexity of recurrence function using iterative method

I want to find the upper bound time complexity of this function. I know how this is done using the induction method, but I can't find clear steps on how to solve it using the iteration method. ...
3
votes
0answers
15 views

Big-O Notation exponentials

I'm learning about Big-O notation for algorithm runtime, and I need some help understanding one part. I read that for the constant, c, does not matter as the function increases rapidly. Does that ...
2
votes
0answers
14 views

Determining asymptotics of a function given a series of difference-like inequalities

I have a function $f: \mathbb{R}_{\geq 0} \rightarrow \mathbb{R}_{\geq 0}$ and I know it satisfies the following properties. $f(x) \leq \frac{\log{\sqrt{2}}}{2x}$ and for all $A \geq 1$ and $B \geq ...
1
vote
1answer
26 views

Approximation of combination $ {n \choose k} = \Theta \left( n^k \right) $?

Is it a valid to say $$ {n \choose k} = \Theta \left( n^k \right) $$ for any $n$ and $k$? If so, how to prove it? Note: $k$ is not a function of $n$. Note: Observed it here (page 5): ...
0
votes
0answers
21 views

how to estimate $\sum (n,i)$?

How to estimate $\sum\limits_{i=-A}^{A} \binom{n}{i}$ ? This probably relates to the central limit theorem and the proof of it. But I want good estimates, also for small values (not just limits to ...
1
vote
0answers
13 views

Prerequisites to reading *Convergence of Probability Measures* by Patrick Billingsley.

I want to improve myself in asymptotic theory regarding the realm of probability. I tried reading Convergence of Probability Measures by Patrick Billingsley but right off the bat the De ...
1
vote
1answer
29 views

Elementary proof of an estimate on $\zeta$

I saw somewhere that If $s=\sigma +it$ where $\sigma >0$ and $t\in \mathbb R$,$x\geq |t|/\pi\implies \zeta(s)=\displaystyle \sum_{n\leq x} \frac{1}{n^s}+\frac{x^{1-s}}{s-1}+O(x^{-\sigma})$ ...
1
vote
0answers
28 views

What does $\mathbb P(\overline{\mathbf X} = \mathbf x)$ mean

I am reading Peter Hall's "the bootstrap and edgeworth expansion". In Theorem 2.3 on page 57, it claims that if the characteristic function $\chi$ of a $d$-dimension random variable $\mathbf X$ ...
3
votes
1answer
55 views

Method of Steepest descents integral

I am looking to evaluate the following asymptotic integral: Find the leading term of asymptotics as $\lambda\to\infty$ $I(\lambda)=\int_0^1\cos(\lambda x^3)dx$ Using method of steepest descents ...
6
votes
0answers
25 views

If $p$ is a positive multivariate polynomial, does $1/p$ have polynomial growth?

I wanted to ask a separate question to focus on an elementary issue from my question Does the inverse of a polynomial matrix have polynomial growth?. Let $p : \mathbb{R}^n \to \mathbb{R}$ be a ...
2
votes
1answer
88 views

Show that $1/\zeta(2k) = \sum_{m \le K} \mu (m)/m^{2k} + O(1/K)$

Show that $1/\zeta(2k) = \sum_{m \le K} \mu (m)/m^{2k} + O(1/K)$. I have already proved that $1/\zeta(s) = \sum_{m=1}^{\infty} \mu (m)/m^s$. But how do I show that if $k\ge 1$, $1/\zeta (2k) = ...
1
vote
0answers
32 views

A combinatorial way to understand $\sum \log^2 n $

Stirling's formula has many derivations using the factorial function: $$ \log N! = \sum_{n=1}^N \log n = \sum_{n=1}^N \sum_{m=1}^n \bigg( \log m - \log (m-1) \bigg) = \sum_{n=1}^N \sum_{m=1}^n - ...
0
votes
0answers
41 views

Approximation of integral as integral range tends to 0

I would like to approximate $\int_{0}^{x}t^{-2}e^{t}\mathrm{d}t$ (maybe find the first two terms) as $x\rightarrow0$. I can't seem to do it by "divide and conquer" or any method. Any suggestion would ...
0
votes
0answers
9 views

Code that Creates a Monotonic Array

I'm not sure whether this belongs on StackOverflow or here. Suppose I have an infinite (indexed from $-\infty$ to $\infty$) array of random doubles x[]. They are ...
0
votes
1answer
20 views

Stokes phenomenon of the Airy function

I am now trying to understand what the so-called stokes phenomenon means. In this page Stokes phenomenon, it reads that `` For large $x$ of given argument the solution (of the Airy equation)can be ...
0
votes
2answers
24 views

Finding the roots and the rescaling of an equation

This question is taken from Hinch's book on perturbation. I need to find the rescalings $x=\delta X$ and the roots of the equation $\epsilon^2x^3+x^2+2x+\epsilon=0$ I have found to possible ...
0
votes
0answers
24 views

Long division for multipolynomial expression, little o notation

I have this expression: $$\mathrm{Exp}=\frac{d^3(-12a^4)+d^2(4a^4-16a^3)+d(4a^3-6a^2-a)}{d^3(-12a^4+12a^3)+d^2(4a^4-20a^3+16a^2)+d(4a^3-11a+7a)+(1-2a+a^2)}$$ Is there any way I can take the second ...
0
votes
1answer
32 views

What algorithm can sort the first sqrt(n) elements of an array in O(n) time?

I want to partially sort an array of $n$ elements to get the first $\sqrt{n}$ elements sorted, and it has to be done in $O(n)$ time. The complexity $O(n)$ seems to imply that it is necessary to go ...
0
votes
0answers
12 views

(Empirical likelihood method) Find the order of a parameter given a set of constraints

Firstly we assume that $X_1,...X_n$ are order statistics($X_i\leq X_{i+1}$) from an i.i.d sample of random variables and let $r$ be integer and $r\geq1$. Start with the equation (1) \begin{equation} ...
0
votes
1answer
26 views

If $nE\|X_n-Y_n\|^2=o(1)$, why $\sqrt{n}(X_n-Y_n)=o_p(1)$ [closed]

How to show that if we have $nE\|X_n-Y_n\|^2=o(1)$, then $\sqrt{n}(X_n-Y_n)=o_p(1)$? Here $X_n,Y_n$ are two random elements.
2
votes
1answer
31 views

Evaluating the leading term of asymptotics

I am struggling with this problem where we're asked to use Laplace's method: Find the leading term of the asymptotics of the following intergral for $\lambda\to\infty$: $$\int_0^{\infty} ...
2
votes
0answers
15 views

Asymptotics of Laplace transform at minus infinity

I am interested in relating the asymptotic behavior of a function $f(t)$ for large values of $t$ with the asymptotic behavior of its Laplace transform $\hat{f}(s)$ for small values of $s$. In practice ...
-1
votes
1answer
38 views

Multiplying logarithms of different bases [closed]

How do you multiply the following logs... $$\log_5(n) * \log_2(n)$$
8
votes
1answer
191 views

Complexity $O(n^3)$ vs $O((\log n)^4))$

I would like to prove that $O(n^3)$ is bigger than $O((\log n)^4)$. I thought that I can divide both powers with 4 so it is $$O\left(n^{\frac{3}{4}}\right)$$ vs $$O(\log n)$$ but then I don't know ...
1
vote
0answers
20 views

Show that $f(b^i n) \le c^i f(n)$

Let $f$ be a b-smooth function. Let $c$ and $n_0$ be constants such that $f(b n) \le c f(n)$ $\forall $ $n \ge n_0$. Show that $\forall $ $ i \in \mathbb{N}, f(b^i n) \le c^i f(n)$ I thought I should ...
1
vote
1answer
82 views

Integrate 1/ln(ln(x)) asymptotically

I was looking for the asymptotic behaviour of the anti-derivative of $\frac{1}{\ln \ln x}$, in terms of the big-O notation. Wikipedia's list does not have this integral, and Wolfram Alpha says "no ...
2
votes
2answers
60 views

How to find a function that is the upper bound of this sum?

The Problem Consider the recurrence $ T(n) = \begin{cases} c & \text{if $n$ is 1} \\ T(\lfloor(n/2)\rfloor) + T(\lfloor(n/4)\rfloor) + 4n, & \text{if $n$ is > 1} \end{cases}$ A. Express ...
2
votes
1answer
39 views

Largest possible subset primes

Let $q$ be a Sophie Germain prime number, i.e. $2q+1=p$ is prime. Consider the set $\{1,2,3,\ldots,p-1\}$. Then what is the maximum size of a subset of this set, such that the subset contains no two ...
4
votes
0answers
70 views
+500

Asymptotic expression of $\int_{- D}^{D} \frac{\text{tanh}(\xi)}{\xi -\omega}\mathrm{d}\xi$

How to derive the following asymptotic expression ($|\omega| \ll D $)? $${\cal{P}}\int_{- D}^{D} \frac{\text{tanh}(\xi)}{\xi -\omega}\mathrm{d}\xi \approx ...
2
votes
0answers
33 views

The series may converge, but what about the series / n?

Let $a_i$ be a positive sequence such that $a_i \to 0$. I know that the series $\sum_{i=1}^\infty a_i$ may be divergent. But what about the series divided by $n$; does the following go to 0? ...
1
vote
1answer
26 views

About the equivalence of two asymptotic probabilistic statements

Let $g(n)$ be some monotone increasing function of naturals, and let $X_n$ be a sequence of positive random variables. Consider the following two claims: Claim 1. $\exists f=o(g(n)),\ ...
6
votes
0answers
47 views

Show that $1^k+2^k+…+n^k$ is $O (n^{k+1})$.

Let $k$ be a positive integer. Show that $1^k+2^k+...+n^k$ is $O (n^{k+1})$. So according to the definition of big-$O$ notation we have: $$1^k+2^k...+n^k ≤ n(n^k) = n^{k+1}$$ whenever $n>1$ Is ...
0
votes
3answers
64 views

Show that $(x^3+2x)/(2x+1)$ is $O(x^2)$

Show that $(x^3+2x)/(2x+1)$ is $O(x^2)$ The definition says: We say that $f(x)$ is $O (g(x))$ if there are constants $C$ and $k$ such that $$\mid f(x) \mid \leq C \mid g(x) \mid$$ whenever $x > ...
0
votes
0answers
26 views

uniform limits and asymptotic equivalence

I am told that $\frac{f(\lambda r)}{f(r)}$ tends to 1 uniformly in $\lambda$. I also know that $x(t)$ is asymptotically equivalent to $ct$, so $x(t)\sim ct$. How can I show that $\frac{f(x(\lambda ...
0
votes
0answers
30 views

To determine asymptotic value of funtion for large N

To simplify the below expression as a function of m and N with m much less than N. $f(m,N)=\sum_{a=1}^{(N-m)/2} \binom{0.5*(N+m)-1}{a} \binom{0.5*(N-m)-1}{a-1} * (x)^{2a} * (y)^{N-2a} $ where ...
1
vote
0answers
31 views

Asymptotic Formula for Sum

I am trying to find an asymptotic formula for the sum of the following: $\sum _{x=1}^{\infty } x \left(\left(1-\frac{\Gamma (x,\lambda )}{\Gamma (x)}\right)^n-\left(1-\frac{\Gamma (x+1,\lambda ...
0
votes
1answer
15 views

natural logarithmic to asymptotic order

Say we have an equation $\lambda_{\epsilon}(s)=-\frac{1}{\pi s^2}\ln(1-\epsilon)$ $\forall s\in (0,(M \mathcal{k})^{-\frac{1}{\alpha}})$ where $s$ can be obtained by $s=(M ...
2
votes
1answer
34 views

Large and small time PDE solution

I have the following solution for a PDE $$ u(x,t)=(2x+4t-10)+2e^{\frac{-1}{2}t}+\sum_{n=1}^{\infty} \frac{(-1)^n cos(\frac{n\pi}{2}x)e^{\frac{-1}{4}n^2\pi^2t}}{n^3\pi^3(n^2\pi^2-2)} $$ I want to ...
0
votes
2answers
27 views

Why can any values of C and N be chosen for the proof of Big-Oh?

In my CS course, they have taught us that, when proving Big-Oh, you can choose any positive integers to be C and k, following the definition. Based on that, they have taught us two different ways of ...
1
vote
1answer
24 views

Asymptotic behaviour of sequences

Could anyone explain in details how these approximations as $n \to \infty$ are found? ($a$ is a positive real number) ${x_n} = \frac{1}{n}\left( {\frac{a}{3} - \frac{3}{2}} \right) + O\left( ...
3
votes
1answer
42 views

Help understanding the complexity of my algorithm (summation)

As an exercise, I wrote an algorithm for summing the all elements in an array that are less than i. Given input array A, it produces output array B, whereby B[i] = sum of all elements in A that are ...
1
vote
1answer
14 views

Asymptotic stopping time for a ball-drawing problem

Take two different boxes, one with $N$ red balls and one with $N$ blue balls. Remove balls one at a time from either box with equal probability. When only one color is left, the (expected value of ...
0
votes
0answers
13 views

Limit of an indeterminated form?

I want to find: $$\lim_{t\to\infty}X_{t}$$ where: $$X_{t} = \frac{A_{t}^{a}}{B_{t}}$$ I know that: $$\lim_{t\to\infty}A_{t}=0$$ and $$\lim_{t\to\infty}B_{t}=0$$ Can I say with certainty that: ...
1
vote
1answer
28 views

Approximation of a generlized hypergeometric function for large parameters

I am looking for an approximation of a generalized hypergeometric function of the type $\, _0F_4$. I've stumbled upon the following approximation : assuming that none of a1,a2,…,ap is a nonpositive ...
0
votes
0answers
16 views

Doubt on asymptotics of continous functions (little-o notation and taylor expansion).

Suppose I have $e^{(\frac{1}{n}b + o(\frac{1}{n}))}$ then $\lim_{n \rightarrow \infty} = e^0 = 1$ so $$e^{(\frac{1}{n}b + o(\frac{1}{n}))} = o(1) +1$$ But if I take the Taylor expansion of ...
0
votes
0answers
16 views

Solution for asymptotic parametric equation

Say I have the following equation: \begin{equation} f(x) = A(t)^{c}g(x)h(x) \end{equation} where $\lim_{t\rightarrow \infty} A(t) = \infty$. Very importantly, $x \in [0,1]$. I want to find the ...
2
votes
0answers
43 views

Question related to the ballistic motion

A point mass will move in the gravitational field of the Earth according to the equation $$\ddot R =-\frac{GM_eR}{|R|^3},$$ where $R$ is the position vector of the point mass measured from the ...
2
votes
0answers
42 views

Asymptotic expansion of root of $\epsilon x \tan(x)=1$

Indicate a range of roots of $\epsilon x \tan(x)=1$ for which it is impossible to get an approximation using expansions. Since $\epsilon$ is small, I think for the equation to hold, we need ...
1
vote
2answers
48 views

A further question on asymptotic expansions of all real roots of xtan(x)=ϵ

I have asked a related question here How to find asymptotic expansions of all real roots of $x \tan(x)=\epsilon?$, however, when I discussed with my adviser today, he argued the solution is flawed. ...