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
3answers
79 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 ...
1
vote
2answers
38 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
1answer
7 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 ...
0
votes
1answer
12 views

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

Similar but different from the problem here: Find numbers in a set whose sum equals x I have an unsorted set S of real numbers, and need to sum elements from S to find the real number X; However, It ...
1
vote
1answer
42 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 ...
7
votes
1answer
85 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 ...
4
votes
1answer
73 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
30 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 ...
2
votes
0answers
35 views

Taylor approximation of a discrete function

Might be a quite stupid question, I'm not sure: Does Taylor Expansion also work if we have a discrete function. Does a discrete function also have something like a Taylor Expansion? I'd like to ...
9
votes
1answer
218 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
73 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
27 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
72 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
0answers
16 views

non-dimensional equation [on hold]

Consider non-dimensional 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.$ Determine to ...
24
votes
0answers
508 views
+100

On the number of complete and gap-free compositions

This is a longish post about something that has been haunting me for a while about a kind of restricted composition, namely gap-free and complete compositions. First, I will define the terms that are ...
1
vote
1answer
28 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
21 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
447 views
+50

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
8
votes
1answer
230 views
+50

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
3answers
26 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
123 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
39 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
103 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
42 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
54 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
47 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 ...
1
vote
1answer
30 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
36 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
35 views

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

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

Solving a recurrence realtion using backward substitution.

So I've been trying my best to do this, and I have made some good progress, I just need to know if what I have done is correct and if not, what the hell am I doing wrong? :P I start off with this ...
1
vote
1answer
214 views

Asymptotic Matching for boundary layer problem

The question asks to find a global approximation to the leading order of $\epsilon$. $\epsilon y'' + xy' + \epsilon y =0$, with boundary conditions $y(0)=1,y(1)=-1$. I assumed it's a boundary layer ...
2
votes
4answers
432 views

Prove that $3^n$ is not $O(2^n)$

I have this question in my assignment. I need to prove, using only the definition of $O(\cdot)$, that $3^n$ is not $O(2^n)$. It is obviously true for any $n \geq 1$. To prove $3^n \in O(2^n)$, we ...
2
votes
1answer
39 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 ...
1
vote
1answer
76 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)$.
3
votes
2answers
206 views

The geometric mean of primes less than or equal to $x$

I want to show that the limit of the geometric mean of primes less than or equal to $x$ is $e$ as $x \to \infty$. Is this correct? Using the product law of logarithms we have $$\ln \prod\limits_{p ...
1
vote
1answer
50 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
78 views

“Balancing” two infinities

Given these two computational complexities of 2 algorithms: $\exp(O(\sqrt{\log n \log \log n}))$ $O(\sqrt{\exp n} / \log{ \sqrt{ \exp n} })$ where I imagine the first one goes to infinity slower ...
1
vote
0answers
29 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$. ...
0
votes
2answers
20 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
48 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$ ...
2
votes
1answer
28 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$. ...
3
votes
0answers
72 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
34 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
23 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?
1
vote
0answers
43 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 ...
1
vote
1answer
38 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 $$ ...
4
votes
2answers
235 views

Is there a function that only generates primes?

The title sums it up: does there exist a "nice" injective function $f(n)$ such that $f(n)\in\mathbb P$ for all $n\in\mathbb N$? I'm having difficulty specifying exactly what I want "nice" to mean, ...
-2
votes
0answers
23 views

prove that θ(n-1)+ θ(n)= θ(n)

I need to prove that statment with big Theta defenition.. θ(n-1)+ θ(n)= θ(n) I have tried many things but cant prove that with defenition of theta
-1
votes
1answer
37 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 ...