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
4answers
60 views

Why is $\lim\limits_{x \to +\infty}\frac{x \sqrt{x+2}}{\sqrt{x+1}} - x = \frac12$?

I need to evaluate this limit: $$\lim_{x \to +\infty}\frac{x \sqrt{x+2}}{\sqrt{x+1}}-x$$ to calculate the asymptote of this function: $$\frac{x \sqrt{x+2}}{\sqrt{x+1}}$$ which, according to the class ...
0
votes
0answers
12 views

Hypergeometric function how to detect blow up for large arguments

I have to study 11 solutions to ODEs containing multiple hypergeometric functions of type: $${}_2F_2 \left(\begin{array}{c} a_1,a_2 \\ b_1,b_2 \\ \end{array} ;z \right).$$ My main ...
2
votes
3answers
73 views

Show that $(-1)^{n}\left(\sqrt{n+1}-\sqrt{n} \right)=\tfrac{(-1)^{n}}{2\sqrt{n}}+\mathcal{O}\left(\tfrac{1}{n^{3/2}} \right)$

I would like to show that : $$\fbox{$(-1)^{n}\left(\sqrt{n+1}-\sqrt{n} \right)=\dfrac{(-1)^{n}}{2\sqrt{n}}+\mathcal{O}\left(\dfrac{1}{n^{3/2}} \right)$}$$ by starting from the left side and get ...
5
votes
2answers
62 views

Show that $\dfrac{(-1)^n}{n+(-1)^n\sqrt{n+1}}=\dfrac{(-1)^n}n+\mathcal{O}\left(\dfrac{1}{n^{3/2}}\right)$

How can i prove that $$\frac{(-1)^n}{n+(-1)^n\sqrt{n+1}}=\frac{(-1)^n}{n} +\mathcal{O}\left(\dfrac{1}{n^{3/2}}\right)\tag{$*$}$$ using the following method : note that : $(1+x)^{\alpha}=1+\...
1
vote
3answers
97 views

Show $\sum_{k=1}^{n}\frac{1}{k}\sim \ln(n)$

there is an example of how we apply Integral test for convergence Theorem: Consider an $n_{0}$ and a non-negative, continuous function $f$ defined on the unbounded $[n_0,+\infty[$, on which it ...
3
votes
0answers
19 views

$\sup\left(\frac{\log(\mbox{ lcm }(1,2,\ldots,k))}{k}\right)$ for $k\in \Bbb{Z}, k>1$

In a previous question Asymptotic growth of l.c.m. of all integers below $k$, it was noted that using the Prime Number Theorem you can prove that $$ \log(\mbox{ lcm }(1,2,\ldots,k)) =k+\mbox{ o}(k)$$ ...
7
votes
3answers
107 views

Trace norm of a triangular matrix with only ones above the diagonal

For $n\in\mathbb N^*$, we consider the triangular matrix $$ T_n = \begin{pmatrix} 1 & \cdots & 1 \\ & \ddots & \vdots \\ 0 & & 1 \end{pmatrix} \in M_{n,n}(\mathbb R) \,. $$ ...
1
vote
0answers
19 views

Solving ODE with irregular singular point

I want to solve the following ODE $$x''(z)+ \frac{\frac{d}{dz} \left(\frac{f(z)}{z^2}\right)}{\frac{f(z)}{z^2}}x'(z)+\frac{\omega^2}{(f(z))^2}x(z)=0$$ where $$f(z) = 1- 4 \left(\frac{z}{z_*}\right)^...
1
vote
0answers
56 views

nature of series $\sum_{n\geq 0}(-1)^{n}u_n $

Let $(u_n)_{n\in\mathbb{N}}$ be sequence defined as follows: $$\left\{ \begin{cases} u_0\in\mathbb{R}^{+}\\\forall n\in\mathbb{N},\quad u_{n+1}=\dfrac{e^{-u_n}}{n+1}\\ \end{cases} \right\}$$ ...
2
votes
0answers
19 views

Asymptotic growth of l.c.m. of all integers below $k$

In a recent question Proof related to Harmonic Progression it was shown that if $m_1, m_2 \ldots m_k$ are positive integers such that $m_1 < m_2 < \ldots < m_k$ and $$ \left\{\frac1{m_1}, \...
0
votes
0answers
27 views

Minimum eigenvalue of a sum of symmetric matrices

Let $\{v_i\}$ be some orthonormal basis in $\mathbb{R}^n$, and let $\{w_i\}$ be a set of positive weights such that $\sum_{i=1}^n w_i = 1$. I am interested in bounding the smallest eigenvalue of the ...
2
votes
3answers
116 views

How can I show this sequence $u_n$ is divergent: $u_n=\exp( n\log n-(n+\epsilon)\log(n+\epsilon))$

How can I show this sequence $u_n$ is divergent: $$u_n=\exp( n\log n-(n+\epsilon)\log(n+\epsilon))\quad n\in \mathbb{N}^*;\quad \epsilon \in (0,1)$$ My attempts: \begin{align*} u_n&=\exp( n\log ...
5
votes
2answers
45 views

Show $\ln\left(\frac{n+(-1)^{n}\sqrt{n}+a}{n+(-1)^{n}\sqrt{n}+b} \right)=\frac{a-b}{n}+\mathcal{O}\left(\frac{1}{n^2} \right) $

I would like to prove the following: $$\ln\left(\dfrac{n+(-1)^{n}\sqrt{n}+a}{n+(-1)^{n}\sqrt{n}+b} \right)=\dfrac{a-b}{n}+\mathcal{O}\left(\dfrac{1}{n^2} \right) $$ My attempt i tried this way ...
10
votes
1answer
86 views

A pair of sequences defined by mutual addition/multiplication

Define sequences $\{a_n\},\,\{b_n\}$ by mutual recurrence relations: $$a_0=b_0=1,\quad a_{n+1}=a_n+b_n,\quad b_{n+1}=a_n\cdot b_n.\tag1$$ The sequence $\{a_n\}$ begins: $$1,\,2,\,3,\,5,\,11,\,41,\,371,...
1
vote
1answer
19 views

Show $\sin\left(2\pi\sqrt{n^2+(-1)^{n}} \right)=\frac{(-1)^{n}\pi}{n}+\mathcal{O}\left( \frac{1}{n^2}\right) $

I would like to prove the following: $$\sin\left(2\pi\sqrt{n^2+(-1)^{n}} \right)=\dfrac{(-1)^{n}\pi}{n}+\mathcal{O}\left( \dfrac{1}{n^2}\right). $$ My attempt: \begin{align*} \sin\left(2\pi\sqrt{n^...
5
votes
1answer
30 views

Show $\cos\left( \pi n^{2}\ln\left(\frac{n}{n-1} \right) \right)=(-1)^{n+1}\frac{\pi}{3n}+\mathcal{O}\left( \frac{1}{n^2}\right) $

I would like to show : $$\cos\left( \pi n^{2}\ln\left(\dfrac{n}{n-1} \right) \right)=(-1)^{n+1}\dfrac{\pi}{3n}+\mathcal{O}\left( \dfrac{1}{n^2}\right) $$ by starting from the left side and get the ...
1
vote
1answer
26 views

Show that $(-1)^{n}\left( (n+1)^{\frac{1}{n+1}}-n^{\frac{1}{n}}\right)=\mathcal{O}\left(\frac{\ln(n)}{n} \right) $

I would like to show: $$(-1)^{n}\left( (n+1)^{\dfrac{1}{n+1}}-n^{\dfrac{1}{n}}\right)=\mathcal{O}\left(\dfrac{\ln(n)}{n} \right) $$ Here is my attempt \begin{align*} (-1)^{n}\left( (n+1)^{\dfrac{1}{...
3
votes
1answer
51 views

Proof of Stirling's Formula using Trapezoid rule and Wallis Product

I need a proof of stirling's formula which uses the riemann's sum and trapezoid approximation to come up with $ \frac {n!}{(n/e)^n \sqrt n}$ $ \rightarrow C$ where $C$ is derived from Wallis product. ...
3
votes
0answers
22 views

Closed form asymptotically

The bound for $$\sum_{i=1}^n\binom{n}{i}2^i$$ is $O\left(3^n\right)$ but what will be the bound for $$\sum_{i=1}^{\frac{n}{2}}\binom{n}{i}2^i$$ Any idea how should I proceed?
0
votes
0answers
14 views

On $\sum_{\substack{\zeta(\frac{1}{2}+i\gamma)=0\\0<\gamma<T}}\prod_{n=1}^\infty \left| 1-\frac{(\gamma\log x)^2}{n^2\pi^2}\right|$ as $O(\log x)$

On assumption that the identity (2) for a representation of $\pi(x)$ holds, see here Two Representations of the Prime Counting Function in this site Mathematics Stack Exchange, and since using the ...
0
votes
1answer
22 views

Show that $\frac{(-1)^{n}}{\left(\ln(n)+(-1)^{n}\right)^{2}}=\frac{(-1)^{n}}{\ln^{2}(n)}+v_n\quad \left( v_n\sim -\frac{2}{\ln^{3}(n)} \right) $

I would like to show that : $$\dfrac{(-1)^{n}}{\left(\ln(n)+(-1)^{n}\right)^{2}}=\dfrac{(-1)^{n}}{\ln^{2}(n)}+v_n\quad \left( v_n\sim -\dfrac{2}{\ln^{3}(n)} \right)\\ $$ by starting from the left ...
0
votes
1answer
22 views

Show $ \frac{(-1)^{n}}{n-\ln(n)}=\frac{(-1)^{n}}{n}+\mathcal{O}\left(\frac{\ln(n)}{n^{2}} \right) $

I would like to show that : $$ \dfrac{(-1)^{n}}{n-\ln(n)}=\dfrac{(-1)^{n}}{n}+\mathcal{O}\left(\dfrac{\ln(n)}{n^{2}} \right) $$ by starting from the left side and get the right side My proof: ...
0
votes
1answer
398 views

Growth of functions (Discrete math)

a) Show that $ \frac{x^3 + 2x}{2x+1} \; is \; O(x^2) $ b) Find witnesses $ C \; and\; K $ My answer was : $ x^3 + 2x \le c(x^2)(2x+1) $ $ x^3 \le c(x^2)(2x+1) , \; when \;c=1 , x>1 $ $ 2x \le ...
1
vote
1answer
13 views

Show $(-1)^{n}\ln\left[ \frac{n(n+2)}{n^2-n+1} \right]=3\frac{(-1)^{n}}{n}+\mathcal{O}\left( \frac{1}{n^2}\right) $

I would like to show that : $$(-1)^{n}\ln\left[ \dfrac{n(n+2)}{n^2-n+1} \right]=3\dfrac{(-1)^{n}}{n}+\mathcal{O}\left( \dfrac{1}{n^2}\right) $$ by starting from the left side and get the right ...
4
votes
2answers
63 views

Growth of $\pi(2x) - 2\pi(x)$

In Hardy & Wright's Theory of Numbers (p. 494f in 6th ed.) there's a little discussion following the proof of the prime number theorem. We have $$ \pi(2x) - \pi(x) = \frac{x}{\log x} + o\...
-1
votes
0answers
27 views

How do I obtain the running time for $T(n)=n^2 \sqrt{n}$?

I tried as, $$T(n)=n^2 \sqrt{n} =n^{\frac{5}{2}} $$ On expanding, $$ T(n)=n^{\frac{5}{2}}+n^{(\frac{5}{2})^2}+n^{(\frac{5}{2})^3}+\cdots +n^{(\frac{5}{2})^k} $$ Thus, for $T(1)$ $$n^{(\frac{5}{2})^k}=...
-1
votes
0answers
26 views

Bound on binomial summation

The bound for $\sum_{i=1}^n\binom{n}{i}2^i$ is $O(3^n)$ but what will be the bound for $\sum_{i=1}^{\frac{n}{2}}\binom{n}{i}2^i$. Any idea how should I proceed.
0
votes
0answers
17 views

multi-scale analysis integral constraint

If I have a function $u(x)$ and I am interested in multiscale analysis for $\tilde{u}(\tilde{x},X)$ where $\tilde{x}=x,X=\epsilon x$, in the context of solving some PDE- the differential operators are ...
1
vote
1answer
45 views

Equivalent of $\int_2^{+ \infty} e^{\Gamma (t) \log x}dt$ when $x \to 1$

I wonder if the equivalent : $$ \int_2^{+ \infty} e^{\Gamma (t) \log x}dt $$ for $x \to 1^{-}$ (i.e the first term in the asymptotic expansion) had been studied ? Is it tricky to get an equivalent ?...
1
vote
0answers
16 views

CLRS substitution method “subtracting constant” technique

I'm reading CLRS, and in Chapter 4 it states that if you guess the asymptotic complexity of a recurrence correctly but cannot quite get the mathematical induction work out, a common method to employ ...
7
votes
1answer
476 views

An entire function of strict order 2

Here is a problem from Stein and Shakarchi Complex Analysis, can somebody help me to solve it? I guess we can use Phragmen-Lindelof theorem but I don't know the exact way. Suppose $f(z)$ is an entire ...
1
vote
1answer
23 views

How do I convert the following relation into a recurrence relation?

I am trying to analyse the time complexity of the fast exponentiation method, which is given as $$x^n= \begin{cases} x^\frac{n}{2}.x^\frac{n}{2} &\text{if n is even}\newline x.x^{n-1} &...
2
votes
1answer
33 views

Asymptotic solution of the equation $\gamma_{i+2} + 4\gamma_{i+1} + \gamma_{i} = \frac{Kh^2}{12}$

I'm struggling with the following equation, I'm interested in an asymptotic solution: $$\gamma_{i+2} + 4\gamma_{i+1} + \gamma_{i} = \frac{Kh^2}{12}$$ Where $K$ is known constant, when $h \rightarrow ...
0
votes
1answer
28 views

What is difference between $O(|V|+|E|)$ and $O(|V+E|)$?

Perform DFS over the entire graph. The linear time taken by a size of graph as visiting each node finished is put it on the head of initially empty list is $O(|V|+|E|)$ $O(|V+E|)$ $O(|V|^k)$ $O(\...
1
vote
0answers
14 views

Does make sense define a gauge for the integral $\int_2^x\frac{\sum_{n\leq t}\Lambda(n)}{t}dt$, where $\Lambda(n)$ is the von Mangoldt funtion?

I try encourage to me to study and understand the definition of gauge integral. See for example this reference Schechter, The Gauge integral where is explained the definition with an example. It is ...
-1
votes
0answers
18 views

What the most optimal value for sqrt(n^3+n(sin(n))^2) = Big O(?)?

In class, I was given this question. Here, I will show step by step on how my teacher did it, but I have some questions. So he said to "bound" it. For all n >= 1, he chooses (sin(n))^2 because it is ...
1
vote
1answer
126 views

Proving Lower Bound on Catalan Numbers

I'm a student of computer science and was reading through my algorithms textbook about matrix chain multiplication. It brought up Catalan numbers and I was hoping to prove the lower bounds on it. This ...
2
votes
2answers
51 views

nature of the series $\sum (-1)^{n}n^{-\tan\left(\tfrac{\pi}{4}+\tfrac{1}{n} \right)}$

I would like to study the nature of the following serie: $$\sum_{n\geq 0}\ (-1)^{n}n^{-\tan\left(\dfrac{\pi}{4}+\dfrac{1}{n} \right)} $$ we can use simply this question : Show : $(-1)^{n}n^{-\tan\...
2
votes
3answers
38 views

Can two function be Big-O of each other?

Given two functions $f(n)$ and $g(n)$, is it possible that $f(n) = O(g)$ and that $g(n) = O(f)$? If the answer is yes, I have a follow-up: if $f(n)$ and $g(n)$ are Big-O of each other, does that ...
0
votes
1answer
13 views

How to concretely interpret big O bounds on error for forward euler?

On the wiki page for forward euler (https://en.wikipedia.org/wiki/Euler_method#Local_truncation_error), it describes the local truncation error like so: $\mathrm{LTE} = y(t_0 + h) - y_1 = \frac{1}{2} ...
1
vote
1answer
27 views

Can you provide us an asymptotic for this series involving Mertens functions?

Let for integers $k\geq 1$, the Möbius function denoted by $\mu(k)$, and $M(n)=\sum_{k\leq n}\mu(k)$ the Mertens function, then one can prove easily that $$\sum_{k=1}^n\mu(k)\frac{e^{\mu(k)}+1}{e^{\...
0
votes
2answers
55 views

Asymptotics of $ f_c(n)=\sum_{k=0}^{\lfloor cn\rfloor}{n\choose k} $

Define $$ f_c(n)=\sum_{k=0}^{\lfloor cn\rfloor}{n\choose k} $$ for some fixed constant $c$ (say, $0<c<1/2$). What are the asymptotics of $f_c(n)$ as $n\to\infty$? It seems that this should be ...
1
vote
1answer
89 views

Counting function for sums of three squares

Legendre showed that an integer is the sum of three squares if and only if it is not of the form $4^n(8m + 7)$ for some nonnegative integers $n$ and $m$. However, I have been unable to find any ...
2
votes
0answers
33 views

Asymptotic expansion of elliptic integral

I am trying to find the first 2-3 terms of the asymptotic expansion in terms of 1/ρ of the elliptic integral \begin{equation} I_n(\rho)=\int_0^\frac{h_2}{\rho}\frac{t^{2n}/h_2^{2n}}{(E_n(t))^2\...
4
votes
3answers
128 views

What is the value of $I=\lim_{n \to \infty} \int_0^1 {{1 + nx^2}\over{(1 + x^2)^n}} \log(2 + \cos(x/n))\,dx.$?

Find the integral $I$.....it looks like a good problem which I was not able to solve ....please help... $$I=\lim_{n \to \infty} \int_0^1 {{1 + nx^2}\over{(1 + x^2)^n}} \log(2 + \cos(x/n))\,dx.$$
1
vote
3answers
1k views

Running time (Big O) of counting in binary

What is the total running time of counting from 1 to $n$ in binary if the time needed to add 1 to the current number $i$ is proportional to the number of bits in the binary expansion of $i$ that must ...
1
vote
0answers
23 views

When is $\frac{2 n f(n)}{n !}$ in the order of some fixed power of $n$?

I would like to know when $\frac{2 n f(n)}{n !}$ is $O (n^b)$ where $b$ is a constant. Here, $n$ is a positive integer. My attempt: $$ \frac{2 n f(n)}{n !} = \frac{2 n f(n)}{\sqrt{2 \pi n} (\frac{n}{...
2
votes
1answer
59 views

Show : $(-1)^{n}n^{-\tan\left(\tfrac{\pi}{4}+\tfrac{1}{n} \right)}=\tfrac{(-1)^{n}}{n}+\mathcal{O}\left(\tfrac{\ln(n)}{n^{2}} \right)$

I would like to show that : $$(-1)^{n}n^{-\tan\left(\dfrac{\pi}{4}+\dfrac{1}{n} \right)}=\dfrac{(-1)^{n}}{n}+\mathcal{O}\left(\dfrac{\ln(n)}{n^{2}} \right)$$ My proof: Note that : \begin{...
0
votes
0answers
19 views

Show that $\tfrac{(-1)^{n}}{\cos(n)+n^{\tfrac{3}{4}}}=\tfrac{(-1)^{n}}{n^{\tfrac{3}{4}}}+\mathcal{O}\left( \tfrac{1}{n^{\tfrac{3}{2}}}\right) $

I would like to show that : $$\dfrac{(-1)^{n}}{\cos(n)+n^{\tfrac{3}{4}}}=\dfrac{(-1)^{n}}{n^{\tfrac{3}{4}}}+\mathcal{O}\left( \dfrac{1}{n^{\tfrac{3}{2}}}\right) $$ by starting from the left side ...
4
votes
0answers
48 views

Show that $(-1)^{n}\sqrt[n]{n}\sin(\frac{1}{n})=\tfrac{(-1)^{n}}{n}+\mathcal{O}\left(\tfrac{\ln(n)}{n^{2}} \right)$

I would like to show that : $$(-1)^{n}\sqrt[n]{n}\sin(\frac{1}{n})=\dfrac{(-1)^{n}}{n}+\mathcal{O}\left(\dfrac{\ln(n)}{n^{2}} \right)$$ by starting from the left side and get the right side : My ...