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

Interpreting little-$o$ notation

This is the integrand of a complex integral: $$\frac{o(\zeta - z)}{\zeta - z}$$ The ensuing discussion says that this can be made as small as desired [by confining $\zeta$ close to $z$]. In general ...
3
votes
3answers
70 views

Wouldn't each addition take time $O(n)$?

I am going over the asymptotic runtime of regular matrix multiplication. Here is a lecture slide I am referencing(too much to type out, shown below), from Algorithms Everything makes sense up ...
1
vote
0answers
24 views

help with an asymptotic for a certain product

I'm having difficulty finding an asymptotic formula for the following product: $$ k^{\alpha}\prod_{1 \leq i \leq N \atop i \neq k} (i^{\alpha}-k^{\alpha})$$ where $N$ is a parameter tending to ...
0
votes
1answer
18 views

Asymptotic expansion for the inverse of a matrix-valued function

suppose I have an asymptotic expansion for a matrix-valued function $\psi : \mathbb{C} \to \mathbb{C}^{2 \times 2}$ : $$\psi(\lambda) \sim I + \frac{m_1}{\lambda} + \frac{m_2}{\lambda^2} + \cdots \ \ ...
5
votes
1answer
128 views

Integral asymptotic expansion of $\int_0^{\pi/2} \exp(-xt^3\cos t)dt$ as $x \to \infty$

I have the integral $$I(x)=\int_0^{\pi/2}\exp(-xt^3\cos t)dt$$ and I want to derive the first two terms in the asymptotic expansion for $x\rightarrow \infty$, which should give me ...
14
votes
2answers
501 views

Asymptotic integral expansion of $\int_0^{\infty} t^{3/4}e^{-x(t^2+2t^4)}dt$ for $x \to \infty$

I'm still having a little trouble applying Laplace's method to find the leading asymptotic behavior of an integral. Could someone help me understand this? How about with an example, like: ...
2
votes
0answers
22 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
97 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. ...
0
votes
1answer
13 views

Linking summations with their correct function(s)

Guys can you please guide me step by step on how to link given functions with the functions to choose from. So for example a function $g(n)\in \Theta n^2$ and if there is no match then you say there ...
3
votes
0answers
19 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 ...
0
votes
0answers
28 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
1answer
63 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): ...
1
vote
0answers
22 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 ...
4
votes
1answer
100 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 ...
1
vote
1answer
31 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
35 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 - ...
3
votes
1answer
273 views

A proof of Stirling's Formula

I need to gain understanding of a proof of Stirling's formula. I have read through Tim Gowers' and Terence Tao's but I'm struggling to follow them. How rigorous is this proof, if at all? Thank you. ...
0
votes
0answers
44 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
10 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
28 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
27 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
1answer
63 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
14 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} ...
2
votes
1answer
77 views

Asymptotics of $\sum_{\mathfrak{a}}\frac{n^{k-\epsilon}}{\mathfrak{N}\left(\mathfrak{a}\right)^{r\left(k-\epsilon\right)}}$

In this paper by Brian D. Sittinger, the following claim is made: For an algebraic number field $K$ with norm $\mathfrak{N}$, let $\epsilon=\left[K:\mathbb{Q}\right]^{-1}$. Then, taking the sum over ...
2
votes
1answer
39 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
24 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
100 views
8
votes
1answer
211 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 ...
2
votes
2answers
80 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 ...
1
vote
1answer
90 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
1answer
41 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 ...
6
votes
0answers
121 views

Asymptotic behavior a recursion involving min/max

Usually when I face solving recursions I use generating functions but I'm not aware of any "tools" to use when min/max expressions are involved. For example, I have the following recursive term: ...
1
vote
1answer
27 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)),\ ...
2
votes
0answers
35 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? ...
6
votes
0answers
55 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
68 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
28 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 ...
3
votes
1answer
46 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 ...
0
votes
1answer
19 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 ...
1
vote
0answers
39 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 ...
2
votes
1answer
42 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 ...
10
votes
1answer
346 views

An equivalent for $\int_0^1\left(\frac{1}{\log x}+\frac{1}{1-x}\right)^n\;dx$

Set $$ I_n :=\int_0^1\left(\frac{1}{\log x} + \frac{1}{1-x}\right)^n \:\mathrm{d}x \qquad n=1,2,3,.... $$ We have $$I_1 =\gamma, \quad I_2 =\log (2 \pi) - \frac 32, \quad I_3 = 6 \log A - ...
0
votes
2answers
29 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
30 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( ...
1
vote
2answers
55 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. ...
1
vote
1answer
16 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: ...
2
votes
0answers
46 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 ...
0
votes
0answers
20 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 ...