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

Asymptotic approximation of a certain sum

During calculations of an expectation of some random variable, I have encountered the following sum: \begin{equation} \sum_{t=2}^{n+1} \frac{t(t-1) \cdot n!}{(n-t+1)!\cdot n^t} \end{equation} I ...
3
votes
2answers
48 views

Asymptotic behaviour of the number of sign changes in the sequence $\cos n\alpha$

Let $0$ $\leq$ $\alpha$ $\leq$ $\pi$. Denote by $V_n$$(\alpha)$ the number of sign changes in the sequence ${u_n}$ where $u_n$ $=$ $\displaystyle \cos n\alpha$. Then find the limit of the sequence ...
0
votes
1answer
60 views

How many self-complementary graphs are there of a given size?

How many self-complementary simple graphs are there on $n$ vertices, up to isomorphism? Denoting this by $S(n)$, it is clear that $S(n)=0$ unless $|K_n|=\frac{n(n-1)}2$ is even, which is when $n=4k$ ...
0
votes
1answer
45 views

Is this Asymptotic Statement true?

Is this statement true? If so, how can I prove it? If not, why not? $$ \frac{n^2}{\log{(n)}} \in \Theta(n^2) $$ Recall the definition of Big Theta asymptotic notation: $f(n) \in \Theta(g(n))$ means ...
1
vote
1answer
29 views

Why does the asymptotic equation of the modified Bessel of the second kind (Iv) have an imaginary part?

This is a follow up to this question. How does one arrive at the asymptotic expressions for the bessel functions? After looking at: G. N. Watson, "A Treatise on the Theory of Bessel Functions", 2nd ...
0
votes
1answer
10 views

A question on an asymptotic combinatorial expasion

Suppose we are given $(\lambda a + \bar{\lambda}b+O(\lambda^2))^{n}$, where $0 < \lambda < 1$ and $\bar{\lambda} := 1-\lambda$; also, $0 < a,b < 1$. $O(\cdot)$ is the traditional Big-Oh ...
1
vote
1answer
42 views

Given a set $S$, find any $N$ numbers than sum to $X$

Similar but different from the problem here. I have an unsorted set $S$ of real numbers, and need to sum elements from $S$ to find the real number $X$; However, It could be from $1$ to $N$ elements ...
1
vote
1answer
92 views

Asymptotics of sum of Binomial Coefficients (Binomial distribution) - Poisson approximation?

Let $$f(n):=\sum_{i=k}^n {n \choose i } p^i (1-p)^{n-i}$$ where $k\geq 2$ is a fixed Parameter and $p=p(n) \in (0,1]$ depends on $n$ where $np\leq 1$. We consider $n \rightarrow \infty$. I've found ...
2
votes
1answer
42 views

Source needed: Does asymptotic normality yield asymptotic unbiasedness and consistency?

Assume that $$\sqrt{n}(\hat g - g(\theta)) \xrightarrow{d} Z, $$ where $Z$ is $N(0,\sigma^2)$. Does this already imply asymptotic unbiasedness and/or consistency, i.e., $$ E[\hat g] \rightarrow ...
1
vote
1answer
42 views

Asymptotic behavior of $\pi (x)-\frac{x}{\log x}$

What is the asymptotic behavior of the function given below. $$f(x)=\pi (x)-\frac{x}{\log x}$$ $$f(x)=O(g(x))$$ What can be $g(x)$? Also what is the asymptotic behavior of the $h(x)=f(x)-g(x)$. My ...
1
vote
2answers
68 views

How does one arrive at the asymptotic expressions for the bessel functions?

It is known that Bessel functions for large arguments will behave as exp or cos/sin however I was wondering how does one arrive at those results. The motivation being that I would like to use these ...
4
votes
2answers
101 views

What does this $\asymp$ symbol mean? (subject: analytic number theory)

I'm reading a survey article by Andrew Granville on analytic number theory. On page 22 of the paper, there appears a strange looking symbol, undefined. I've circled it in red in the screenshot ...
1
vote
1answer
33 views

How to find an asymptotic formula for $f(n)=\sum_{k=1620}^{n}(\log\log\log k)^{2}$?

How to find an asymptotic formula for function given below. $$f(n)=\sum_{k=1620}^{n}(\log\log\log k)^{2}$$
5
votes
1answer
107 views

Asymptotics of an oscillatory integral with a linear oscillator

I am interested in asymptotic results for $$ S(p) = \int_0^1 \frac{y \sqrt{1-y^2}}{(\varepsilon^2-1)y^2+1} \sin(py) dy, $$ i.e. a result that is valid as $p\rightarrow\infty$. The parameter ...
1
vote
1answer
23 views

Estimation higher order

Consider non-dimensional differential equation for the height at the highest point is given by \begin{equation} h(\mu)= \frac{1}{\mu}- \frac{1}{\mu^2} \log_e(1+\mu) \end{equation} $0<\mu\ll 1.$ ...
0
votes
3answers
38 views

Big O question related to nested loop

So i have code that is a nested loop and the outside loop executes n times but the inside loop executes $n\sqrt{n}$ times. So would my worst case scenario still be $O(n^2)$?
3
votes
2answers
146 views

Big O and function composition

On the last page of this document, a property of Big O operations is listed which says that if $f_1(n)$ = O($g_1(n)$) and $f_2(n)$ = O($g_2(n)$) then $f_1$o $f_2$ = O($g_1$ o $g_2$) Why is ...
0
votes
1answer
50 views

Laplace's Method Integration

Consider the integral \begin{equation} I_n(x)=\int^2_1 (\log_{e}t) e^{-x(t-1)^{n}} \, dt \end{equation} Use Laplace's Method to show that \begin{equation} I_n(x) \sim \frac{1}{nx^\frac{2}{n}} ...
3
votes
2answers
79 views

Integration by expansion

Consider the integral \begin{equation} I(x)= \frac{1}{\pi} \int^{\pi}_{0} \sin(x\sin t) \,dt \end{equation} show that \begin{equation} I(x)= \frac{2x}{\pi} +O(x^{3}) \end{equation} as ...
0
votes
1answer
50 views

Laplace's Method (Integration)

Consider the integral \begin{equation} I(x)=\int^{2}_{0} (1+t) \exp\left(x\cos\left(\frac{\pi(t-1)}{2}\right)\right) dt \end{equation} Use Laplace's Method to show that \begin{equation} I(x) \sim ...
3
votes
0answers
63 views

Saddle point method: a rigorous proof?

I am trying to prove in a fully rigorous way the Saddle Point method for holomorphic functions of 1 complex variable. In books I find only complicated general statements or non-rigorous proofs. Hence ...
10
votes
2answers
441 views

How prove this sequence $a_{n}=\sqrt{n}+\frac{1}{2}-\frac{1}{8\sqrt{n}}+o\left(\frac{1}{\sqrt{n}}\right)?$

let sequence $\{a_{n}\}$ such $$a_{1}=1,a_{n+1}=1+\dfrac{n}{a_{n}}$$ show that: $$a_{n}=\sqrt{n}+\dfrac{1}{2}-\dfrac{1}{8\sqrt{n}}+o\left(\dfrac{1}{\sqrt{n}}\right)?$$ This result is china student ...
0
votes
1answer
51 views

Expansion of Integration

Consider the integral \begin{equation} I(x)=\int^{2}_{0} (1+t) \exp\left(x\cos\left(\frac{\pi(t-1)}{2}\right)\right) dt \end{equation} show that \begin{equation} I(x)= 4+ \frac{8}{\pi}x +O(x^{2}) ...
1
vote
1answer
31 views

How do you define computational complexity abstractly?

Let the problem we're studying be $f : X \to Y$. Say, I don't know what I want to define time-complexity with respect to, I just know I have a map $|\cdot| : X \to \Bbb{R}$, such that $|\cdot| \geq ...
3
votes
2answers
49 views

Short argument for asymptotic value of parameter integral

I want to find the main term of the asymptotic expansion for $x\to 0^+$ for $$f(x)=\int_0^{\pi/2} \dfrac{\cos t}{t+x}dt.$$ Now, clearly, the problem is at $t=0$ and the cosine is almost $1$ ...
0
votes
2answers
39 views

Discrete Mathematics: Prove that f(x) is in O(x)

Prove that $$\frac{2x^{2}+x}{x+1}$$ is in $O(x)$
2
votes
1answer
44 views

asymptotics of this sum $ x \to 0 $

given the sum $$ \sum_{n=0}^\infty \frac{\exp(-nx)}{n+a} =f(x) $$ what would be the asymtptic of this series ?? for $a=1$ i believe this series goes as $ f(x) \sim \frac{1}{x}+ \gamma $ for every ...
0
votes
1answer
112 views

Prove that there exists a constant $C$ such that $[z^n]\exp(z/(1-z)) = O(\exp(C\sqrt{n})) $ [closed]

Prove that there exists a constant $C$ such that: $$[z^n]\exp(z/(1-z)) = O(\exp(C\sqrt{n})).$$ The bound of $z$ is $\vert z \vert<\frac14$
1
vote
1answer
59 views

Bound summation of successive square roots

What is a tight upper bound for $f(n)$ where $f(n) = f(\sqrt{n}) + \frac{1}{n}$. One can easily find the following upper bound $O(\lg \lg n)$, however I'm interested in a tight bound. Regards.
1
vote
0answers
63 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
1answer
53 views

Prove or disprove: $(\frac{1}{n})^n(1 - \frac{1}{n})^{n^2-n} \simeq \frac{1}{n!}$ as $n \rightarrow \infty$.

Prove or disprove: $(\frac{1}{n})^n(1 - \frac{1}{n})^{n^2-n} \simeq \frac{1}{n!}$ as $n \rightarrow \infty$. I'm trying to prove the statement by building on my observation that $(1-\frac{1}{n})^n$ ...
3
votes
0answers
107 views

Question about Big O notation for asymptotic behavior in convergent power series

Examples of such use of Big O notation can be found for instance on Wolfram Alpha here. More details on the Wikipedia page. The idea, as I understand it, is that the term between parenthesis in Big O ...
2
votes
0answers
35 views

Question about Big O notation for asymptotic behavior in convergent power series [duplicate]

Examples of such use of Big O notation can be found for instance on Wolfram Alpha here. More details on the Wikipedia page. The idea, as I understand it, is that the term between parenthesis in Big O ...
0
votes
1answer
30 views

Interpreting expression with big-O notation in the exponent ($f(x) = x^{1+O(1)}$)

How should one interpret the notation $f(x) = x^{1+O(1)}$? I'm a bit confused as to what this means. Does it merely suggest that f(x) grows as some integer power of x?
0
votes
2answers
22 views

Big Omega — n, n + 100

Given $f(n) = n$ and $g(n) = n + 100$, it seems that f(n) is $O(g(n))$ when $C = 1$ and $k= 0$. That is, for every $n$ from $0$ to infinity, g(n) is strictly larger than f(n). Now, concerning ...
1
vote
1answer
42 views

Integral $\int_{-\infty}^\infty dx e^{-nx^2/2}(z-ix)^n$

$$ I\equiv\mathcal{F}_n(z)=\int_{-\infty}^\infty dx e^{-nx^2/2}(z-ix)^n. $$ Evaluate I for $n \to \infty$ and z real. We can consider $z\geq 0$ due to the symmetry of $\mathcal{F}$ given by $$ ...
-1
votes
1answer
44 views

Prove that |O(2n)-O(n)|=O(n)

I need to prove that statement with the defenition of big O |O(2n)-O(n)|=O(n) Does it can be proven? or not? if i can, so how..in which way? i tried almost ...
0
votes
2answers
49 views

Big-O notation and polynomials

In my text, I am given that the sum of the first n positive integers can be understood in terms of big-O notation. ''Since each of the integers in the sum of the first $n$ positive integers does not ...
1
vote
0answers
119 views

Free lecture notes to Carl Bender's Mathematical Physics video lecture course?

I am just watching Carl Bender's Mathematical Physics video lecture course (about asymptotics and its application in physics) http://www.perimeterscholars.org/328.html which is great! Are there any ...
4
votes
3answers
109 views

Taking Limits with Binomial Coefficients

I am interested in taking the following limit: \begin{equation} \lim_{n \to \infty}\frac{{n/2 \choose m}}{n \choose m}. \end{equation} Provided that $m$ is fixed the solution is: \begin{equation} ...
0
votes
2answers
53 views

Expanding $\ln(1+f(x))$ around $f(x)=0$ when we do not know whether there is an $x$ such that $f(x)=0$.

I want to expand $\ln(1+f_T(x,\theta))$ about $1+f_T(x,\theta)=1$. What I have in mind is something like $$ \ln(1+f_T(x,\theta))=\ln(1)+f_T(x,\theta)-\frac{1}{2} \frac{1}{1+\tilde{f}} ...
0
votes
0answers
15 views

How to determine sub-exponential time growth?

I'm a little bit confused of sub-exponential time growth; consider the definition from Hoffstein's book An Introduction to Mathematical Cryptography: Given input of $k$ bits, then if an algorithm ...
1
vote
0answers
50 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 ...
0
votes
1answer
22 views

Prove the following $\frac{\Omega(f(n))}{\Omega(g(n))} \subseteq \Omega(\frac{f(n)}{g(n)})$

I want to prove the following: $$\frac{\Omega(f(n))}{\Omega(g(n))} \subseteq \Omega(\frac{f(n)}{g(n)})$$ I wonder if its true? What about using $n$ and $n^2$? Any suggestions? Thanks!
2
votes
1answer
31 views

Big O notation preserved under convex functions?

Suppose that the random variable $X_T$ is $O_p(1)$ as $T \rightarrow \infty$, i.e. $\forall \epsilon>0$, $\exists M_\epsilon>0$ such that $\mathbb{P}(X_T>M_\epsilon)<\epsilon$ $\forall T$. ...
0
votes
1answer
32 views

Order functions by speed of their asymptotic growths

We are given list of functions. Task is to sort it by the speed of their asumptotic growth in ascending order. Yes, it's a homework. I already spent some solid amount of time calculating limits. I ...
1
vote
1answer
81 views

What is $O\Big((n+1)!\Big)$?

What is $f(n) = (n+1)!$ which is also $f(n) = (n+1)n!$ in terms of big-O notation? My guess is $O(n \cdot n!)$ but I am not sure. I only know it is certainly $f(n) \in O(n^n)$.
5
votes
2answers
134 views

Use the Euler-Maclaurin summation formula to estimate a summation

$\sum_{k=0}^n \frac{1}{1+\frac{k}{n}}$ How can we estimate it to order $O(n^{-5})$ ?
0
votes
0answers
27 views

Asymptotic distribution of the t statistic

I want to find the asymptotic distribution of the t statistic when (a) we assume equal variances between groups with sample sizes m and n (b) assume unequal variances between groups For part (a) it ...
0
votes
1answer
25 views

Tight bound of worst case performance of algorithm

I am trying to find the "tight bound of an algorithm for the worst case run time. I have found that the upper bound of the worst case is O(n), I have also found that the lower bound for the worst case ...