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

learn more… | top users | synonyms (1)

9
votes
1answer
267 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, ...
5
votes
2answers
752 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
71 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
104 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
58 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
27 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
957 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
81 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
773 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
77 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
150 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$
3
votes
0answers
120 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
58 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}) ...
4
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
35 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
56 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
42 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
4k 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 ...
2
votes
4answers
3k 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
49 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
89 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
308 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
82 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
88 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 ...
0
votes
2answers
41 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
55 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
48 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$. ...
4
votes
0answers
321 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
42 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
45 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
69 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
47 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 $$ ...
5
votes
2answers
294 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, ...
-1
votes
1answer
53 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
223 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 ...
2
votes
0answers
687 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 ...
1
vote
2answers
588 views

List of calculation rules for asymptotic notation?

Background: I am working my way through CLR/CLRS's proof of the master theorem (section 4.4 in the 1st and 2nd editions of Introduction to Algorithms), and I'm doing my own write-up of this proof1 ...
0
votes
2answers
55 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
1answer
24 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!
0
votes
1answer
267 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 ...
0
votes
1answer
124 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 ...
0
votes
2answers
53 views

Asymptotics - Big Omega

I have a question about Asymptotics involving big Omega... How do I need to approach this equation in order to prove it? $$n \cdotΩ(f(n)) = Ω(n\cdot f(n))$$ Thank you very much for your answers!
1
vote
0answers
61 views

Is $\log^* (n+1)^{n+2} \in O(\log^* n)$?

I would like to know if $\log^* (n+1)^{n+2} \in O(\log^* n)$, where $\log^*$ is the iterated logarithm. I tried doing: $ \log^* (n+1)^{n+2} =\\ \log^{*}(\log(n+1)^{n+2})-1 =\\ \log^{*}((n+2) \cdot ...
0
votes
1answer
130 views

Prove $\Omega(f(n)) \subset \Omega(g(n)), iff : g(n)\in \mathcal{O}(f(n)) \wedge f(n) \not\in \mathcal{O}(g(n))$

I want to prove the following $$\Omega(f(n)) \subset \Omega(g(n)), iff : g(n)\in \mathcal{O}(f(n)) \wedge f(n) \not\in \mathcal{O}(g(n))$$ What I did so far is: $$t(n)\in\Omega(f(n)) \rightarrow ...
1
vote
0answers
29 views

Asymptotic estimate for an expression of

\begin{equation} A = \frac{(\frac12-\frac{1}{n})(\frac12-\frac{2}{n})...(\frac12-\frac{t-1}{n})}{(\frac{1}{2}+\frac{1}{n})(\frac{1}{2}+\frac{2}{n})... (\frac{1}{2}+\frac{t}{n})} \end{equation} Can we ...
4
votes
1answer
107 views

On the sum of prime powers

Has anybody investigated the asymptotic growth rate of functions in the form of $$f(z,n)=\sum\limits_{p\le n}p^z$$ For $Re(z)\ge -1$. Of course $f(0,n)=\pi (n)$ has an ocean of research surrounding ...
2
votes
1answer
47 views

asymptotic estimate for this expression

How can I compute an asymptotic estimate for following expression? \begin{equation} A = ...
2
votes
1answer
61 views

Compute summation with a relative error of O(n^-2)

$a(n) = \sum_{i \geq 0} a_i n^{-i}$, how can we compute the value of $a(n)^n$ with a relative error of $O(n^{-2})$?
4
votes
0answers
165 views

WKB and asymptotic behavior of second order differential equation

I want to study the large $x$ solution to a Riccati equation. After listening to the lectures on Mathematical Physics by Carl Bender, I have fallen in love with asymptotic analysis. But, by no means ...
0
votes
0answers
28 views

asymptotics big Omega and O

I have a problem at Asymptotycs.. there is given to me that : $$f(n)+g(n) \in \Omega(t(n))$$ I need to prove with the defenition that: $$\operatorname{abs}(f(n)-g(n))∈O(t(n))$$ How I start ...