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

learn more… | top users | synonyms (1)

1
vote
1answer
18 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
26 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
22 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}{...
0
votes
0answers
11 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
20 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
20 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: ...
1
vote
1answer
12 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 ...
9
votes
1answer
71 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,...
3
votes
1answer
50 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. ...
-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}=...
3
votes
1answer
17 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?
-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
16 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
0answers
15 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 ...
1
vote
1answer
44 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
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
32 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 ...
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 ...
0
votes
1answer
27 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
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 ...
2
votes
2answers
48 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
36 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
26 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^{\...
2
votes
0answers
30 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
118 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
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}{...
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\...
2
votes
1answer
57 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 ...
1
vote
0answers
7 views

$X-x_0=O_p(n^{-1/2})$ implies $g(X)-g(x_0)=O_p(n^{-1/2})$

Suppose that $X$ is a random vector and $x_0$ is a fixed vector such that $$ X-x_0=O_p(n^{-1/2}).\tag{$*$} $$ Let $Y=g(X)$ where $g$ has a continuous gradient that is nonzero at $x_0$. Let $y_0=g(x_0)$...
2
votes
3answers
64 views

Show that $(-1)^{n}\left(\sqrt{n+1}-\sqrt{n} \right)=\tfrac{(-1)^{n}}{2\sqrt{n}}+\mathcal{O}\left(\tfrac{1}{n^{\frac{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^{\dfrac{3}{2}}} \right)$}$$ by starting from the left side ...
5
votes
2answers
56 views

Show that $\dfrac{(-1)^n}{n+(-1)^n\sqrt{n+1}}=\dfrac{(-1)^n}{n}+\mathcal{O}\left(\dfrac{1}{n^{\frac{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^{\frac{3}{2}}}\right)\tag{$*$}$$ using the following method : note that : $(1+x)^{\...
4
votes
3answers
67 views

Convergence of the series $\sum \frac{(-1)^{n}}{n^{\frac{2}{3}}+n^{\frac{1}{3}}+(-1)^{n}}$

To prove that nature of the following series : $$\sum \dfrac{(-1)^{n}}{n^{\frac{2}{3}}+n^{\frac{1}{3}}+(-1)^{n}}$$ they use in solution manual : My questions: I don't know how to achieve ( * ) ...
0
votes
0answers
14 views

Is there a simple way to describe all $O(n)$ algorithms given simple assumptions about the machine?

For example, can all $O(n)$ algorithms (where $n$ is strictly an integer) be described as: for k in 0..f(n): O(1)(k) where $f$ is a linear polynomial in $\Bbb{...
0
votes
1answer
27 views

Evaluating a polynomial that includes a little-o constant exponent

In a paper I am reading, the following assertion is made: N is an odd, positive composite number. Let $I_1 = [\sqrt N - F^{2+o(1)} , \sqrt N + F^{2+o(1)}]$ hold the values of $x$ passed into the ...
1
vote
0answers
28 views

Difference/switch between big/small o in taylor series

for example i only know taylor series with small o is there anyway to switch from small o to big o in taylor series and why when we want to see the nature of some series we use taylor series with ...
7
votes
3answers
94 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
2answers
56 views

Prove/disprove : $\left(1+\dfrac{(-1)^{n}}{\sqrt{n}} \right)^{-1}=\left(1-\dfrac{(-1)^{n}}{\sqrt{n}}+o\left(\dfrac{1}{n}\right) \right)$ [closed]

why we have that \begin{align*} \frac{(-1)^n}{\sqrt{n}}\left(1+\frac{(-1)^n}{\sqrt{n}} \right)^{-1} & =\frac{(-1)^n}{\sqrt{n}}\left(1-\frac{(-1)^n}{\sqrt{n}}+o\left(\frac{1}n\right) \right) \tag{$...
1
vote
1answer
16 views

Big O-Notation Proof Omega and Theta

Consider the following three functions $ f,g,h: \mathbb{N{}} \rightarrow \mathbb{R} $, for which applies: $ f \in \Omega(g) $ and $ g \in \Theta(h) $. Proof or disprove formal that $f \in \Omega(h) $....
1
vote
1answer
70 views

Is it possible to identify this sequence?

Interested by this question, $j$ being a positive integer, I tried to work the asymptotics of $$S^{(j)}_n=\sum^{n}_{k=0}\frac{\binom{n}{k}}{n^k(k+j)}=\frac{\, _2F_1\left(j,-n;j+1;-\frac{1}{n}\...
6
votes
3answers
90 views

Puiseux Expansion of Gamma Function about Infinity

In trying to find interesting proofs that Student's T Distribution converges to the Regularized Normal Distribution when $k$ (the number of desgrees of freedom) grows without bounds (i.e. $= \infty$). ...
-2
votes
2answers
38 views

what is asymptotic behavior of $\sum \frac {1}{\sqrt[\alpha] k}$ [duplicate]

Asymptotic behavior of $$\sum \frac {1}{\sqrt[\alpha] k}$$ for $\alpha=1$? is $\ln k$ what about $\alpha > 1$ ? the suggested link is for $\alpha > \frac{1}{2}$ my question is about $ 0< \...
0
votes
0answers
13 views

Asymptotics of ratio of confluent hypergeometric functions of the second kind.

How can I show that $\frac{U(1-d,1,-1)}{U(-d,1,-1)}=-\frac{1}{d}+\frac{1}{d^{3/2}}-\frac{3}{4d^2}+O\left(\frac{1}{d^{5/2}}\right)$. Where $U(a,b,x)$ denotes the confluent hypergeometric function of ...
0
votes
1answer
45 views

Finding the product of a prime function…

If we take the primes $p_k < n$, and raise them to the highest power possible such that $(p_k)^{r_k} \le n$, what is the lower bounds on $\prod{ (p_k)^{r_k} }$? In other words, what are the ...
3
votes
0answers
30 views

Asymptotic behavior of a function defined via a complex integral

I would appreciate any comment/correction about what I did for the following problem, I would be very thankful if you let me know the parts of it which may not be very precise: Let $g(z)$ be defined ...
0
votes
0answers
14 views

Asymptotic Expansions of a Generalized Hyper-Geometric Function

Let $t>0,x>0$, and $$\{a_1,a_2,a_3\}=\{2, 2, 9/8 - (i t)/2\}$$ $$\{b_1,b_2,b_3,b_4\}=\{1, 1, 3/2, 17/8 - (i t)/2\}$$ We are looking for the asymptotic expansions of a generalized hyper-...
0
votes
1answer
28 views

An asymptotic numeric problem.

Given a large enough integer $N$ is there always a $c\in(0,1)$ such that $$(N+ N^{1-c}){c\ln(e N)}>\ln( N+( N)^{1-c})(N+2 N^c)$$ holds? What is this $c$ explicitly (at least a close approximation ...
0
votes
0answers
37 views

Asymptotics of Inverse Laplace transform of a function with a branch point and singularities

consider the inverse Laplace transform $f(x)=L^{-1}[\tilde{f}]$ of a function $\tilde{f}(s)$. I would really like to find the large-$x$ asymptotics of $f(x)$ for the following case: $$\tilde{f}(s)=\...