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
0answers
17 views

Computing the asymptotic spectrum of a negative distance kernel

Consider the following integral operator: $$K(f) : x \mapsto\int_0^1 K(x,x')f(x') dx', \quad \text{where} \quad K(x,x') = - |x-x'|^{3/2}.$$ The kernel is sometimes referred to as a negative ...
3
votes
2answers
64 views

Why is $\psi(x) = \sum_{n=1}^{\infty} e^{-\pi n^2x} = O(e^{-\pi x})$

We define $\psi(x) = \sum_{n=1}^{\infty} e^{-\pi n^2x}$. Why is it that $\psi(x) = O(e^{-\pi x})$ EDIT: As $ x \to \infty$ (big-oh-notation) I think we can assume that x is positive. I get that ...
0
votes
2answers
27 views

Multiplication of asymptotic approximation

If I know that: $a = (1 - O(\frac{1}{n}))$ and $b = (1 + O(\frac{1}{n}))$, what is the asymptotic approximation of $a\cdot b$? Is answer $ab = (1 - O(\frac{1}{n^2}))$ correct or it is still $ab = (1 - ...
19
votes
7answers
1k views

Is there a formula for $\sum_{n=1}^{k} \frac1{n^3}$?

I am searching for the value of $$\sum_{n=k+1}^{\infty} \frac1{n^3} \stackrel{?}{=} \sum_{n = 1}^{\infty} \frac1{n^3} - \sum_{n=1}^{k} \frac1{n^3} = \zeta(3) - \sum_{n=1}^{k} \frac1{n^3}$$ For which ...
2
votes
1answer
68 views

Asymptotic evaluation of integral method of steepest descent

The question asks to show that the leading term of the integral $$ \int_{-\infty}^\infty (1+t^2)^{-1}\exp\left(ik(t^5/5+t)\right) dt $$ for large $k$ using the method of steepest descent is equal to ...
0
votes
2answers
176 views

How to arrange functions in increasing order of growth rate , providing f(n)=O(g(n))

Given the following functions i need to arrange them in increasing order of growth a) $2^{2^n}$ b) $2^{n^2}$ c) $n^2 \log n$ d) $n$ e) $n^{2^n}$ My first attempt was to plot the graphs but it didn't ...
4
votes
1answer
67 views

Applications of the Exponential Integral?

this is my first time asking a question on here so please forgive me if I have made any formatting mistakes. I have the integral $f(x) = \int_0^\infty \frac{e^{-t}}{x + t} \; dt$ and I have shown the ...
1
vote
0answers
36 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 ...
0
votes
1answer
101 views

Big O Notation Exercise

I'm having a small problem. I'm very new in this section so please bear with me. I understand Big O meaning what everything signifies like the $O(n), O(n^2), O(x^n), O(\log n)$ and $O(1)$. I also ...
0
votes
1answer
30 views

Monotonicity of $f(x)-g(x)$ where $g$ is asymptotically greater than $f$

If $g(x) \succ f(x)$ (or $\lim_{x\rightarrow \infty}\frac{f(x)}{g(x)}=0$), will $g(x)-f(x)$ always be a strictly increasing function?
10
votes
2answers
429 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 ...
1
vote
1answer
16 views

third order recurrence relation with non-constant coefficients

Does anyone know of a paper that may have been written on $3^{rd}$ order recurrence relations with polynomial coefficients, that is, one of the form $$A(n)a_{n+3}+B(n)a_{n+2}+C(n)a_{n+1}=D(n)a_n$$ ...
4
votes
1answer
47 views

How to find the sum of Big-Oh's?

I will admit this is a homework problem, but I'm seriously stuck. I'm not looking for answers, but just any hints as to what to do next. Any tips would be appreciated. I am given: $$f_1(x) = ...
1
vote
0answers
42 views

Computational Complexity

My question is very basic, it is just so that I have a basic grasp of the terminology of algorithm speed. When someone says an algorithm speed is $O(n^2)$ they say that the number of steps of this ...
1
vote
2answers
38 views

Trouble understanding Big O notation for a sum of n integers [duplicate]

This problem is an example in a Discrete Math textbook. How can big-O notation be used to estimate the sum of the first n positive integers? Solution: Because each of the integers in the sum of the ...
0
votes
0answers
25 views

Determining the Asymptotic Order of Growth of the Generalized Harmonic Function?

How should I proceed to determine the order of growth of the generalized harmonic numbers? $$ H_{n}^{(r)} \in \mathcal{O}(?) $$
2
votes
0answers
37 views

Prove that (x+1)! is not O(x!)

Discrete math question which is as follows: Prove that (x+1)! is not O(x!) using only the definition of Big-Oh notation. (Hint!: log(a * b) = (log a + log b)) I used a proof by contradiction saying ...
1
vote
1answer
91 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 ...
1
vote
1answer
37 views

Is This Statement True?

Is it correct to assert that $T(n) \in \Theta(n^2)$ when: $$ \frac{n^2}{\log{(n)}} \leq T(n) \leq \frac{n^2}{\log{(n)}} + n $$
1
vote
1answer
29 views

Power Iteration method for eigenvalues - Show the error is bound

Let $A \in $Sym$_{n}(\mathbb R)$ with eigenvalues $\lambda_i$ such that $|\lambda_1| > |\lambda_2| \geq |\lambda_3 |\geq ... \geq |\lambda_n|$ We define the following process as "Power Iteration": ...
0
votes
1answer
20 views

General questions concerning asymptotic behavior

I have some difficulties understanding asymptotics in general. Is $O(n)$ the same as $O(-n)$? Is $O(f(n))$ the same as $O(cf(n))$ even though we know that $f(n)\leq 1$ for all $n$? I know the ...
1
vote
1answer
24 views

If $p(x)$ is a polynomial of degree d, prove that $p(x) \in \Theta(x^d)$

I just started learning asymptotic notation and I have a problem with this one. Let $p(x)=a_dx^d+a_{d-1}x^{d-1}+.....+a_1x+a_0$ be a polynomial of degree d, with $a_i \in \mathbb{R}$ for $0\leq i ...
3
votes
1answer
32 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 ...
2
votes
4answers
42 views

Why is $\log(n) \in o(\frac{n}{\log(n)})$?

This would be equal to: $\forall c>0: \exists n_0 \in \mathbb{N}: \forall n>n_0: c\log(n) ≤ \frac{n}{\log(n)}$ For $c=1$ this is obvious, because $\log(n) ≤ \sqrt{n} = \frac{n}{\sqrt{n}} ≤ ...
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
58 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$ ...
1
vote
1answer
37 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 ...
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
28 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 ...
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 ...
0
votes
3answers
109 views

Prove that a circle has an infinite number of tangents

It seems obvious that a circle is comprised of the set of all points that are equidistant from one point, and that each point on the circumference of the circle represents a tangent. This seems to ...
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 ...
7
votes
1answer
91 views

Help proving $\sum_{n\le x}{\ln{n}}=x\ln{x}-x+O(\ln{x})$

Just learning a bit about big O notation and have come across this exercise. The notation used is $$\sum_{n\le x}{\ln{n}}=x\ln{x}-x+O(\ln{x})$$ and I am assuming that is equivalent to ...
5
votes
1answer
102 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 ...
2
votes
1answer
41 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 ...
9
votes
1answer
226 views

Analytic number theory primer — sequences and series

For a book like Titchmarsh, or Iwaniec and Kowalski, it seems a thorough knowledge of asymptotics is a prerequisite. What are good books for training oneself in such manipulation of asymptotics, ...
4
votes
2answers
98 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
40 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 ...
3
votes
2answers
78 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 ...
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}$$
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
2answers
486 views

Ratios in big-O notation?

Hi can anyone give me a counter example of the following claim: f(n) = O(s(n)) and g(n)=O(r(n)) imply f(n)/g(n) = O(s(n)/r(n)) Thank you
0
votes
3answers
34 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
142 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}} ...
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$
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
61 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 ...
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}) ...
3
votes
1answer
2k views

how can be prove that $\max(f(n),g(n)) = \Theta(f(n)+g(n))$

how can be prove that $\max(f(n),g(n)) = \Theta(f(n)+g(n))$ though the big O case is simple since $\max(f(n),g(n)) \leq f(n)+g(n)$ edit : where $f(n)$ and $g(n)$ are asymptotically nonnegative ...