# Tag Info

I will present two approaches to this question. The first is less advanced and easier but also yields a less optimal result. First Method Consider the auxiliary sequence $b_n =\sqrt{n+\frac{1}{4}}+\frac{1}{2}$. This is the unique positive solution to the $P_n(X)=0$ where $P_n(X)=X^2-X-n$. ${\bf Lemma~1.}$ For every $n\geq1$, we have $b_{n+1}\geq ... 4 First, the change of variables$t\leftarrow2-t$shows that$I(x)=\int_0^2(3-t)e^{x\,\cos(\pi(t-1)/2)}dt, taking the half sum we conclude that \eqalign{I(x)&=2\int_0^2\exp\left(x\cos\frac{\pi(t-1)}{2}\right)dt\cr &=2\sum_{n=0}^\infty\frac{x^n}{n!}\int_0^2\cos^n\left(\frac{\pi(t-1)}{2}\right)dt\cr ... 4 Note that\eqalign{f(x)&=\int_0^{\pi/2}\frac{1}{t+x} dt-\int_0^{\pi/2}\frac{1-\cos t }{t+x}dt\cr &=\ln\left(\frac{\pi}{2}+x\right)-\ln x- \int_0^{\pi/2}\frac{1-\cos t }{t}dt+ \int_0^{\pi/2}\left(\frac{1}{t}-\frac{1}{t+x}\right)(1-\cos t )dt\cr &=\ln\left(\frac{\pi}{2}+x\right)-\ln x- \int_0^{\pi/2}\frac{1-\cos t }{t}dt+x ... 4 We will show that, fora>0$and$x$in the neighborhood of$0^+$, we have $$f(x)=-\gamma-\psi(a)-\ln(x)+o(x)$$ where$\gamma$is the Euler-Mascheroni constant, and$\psi=\Gamma'/\Gamma$is the Digamma function. Indeed, let us write$fas follows: \eqalign{ f(x)&=\frac{1}{a}+ \sum_{n=1}^\infty\frac{e^{-nx}}{n}+ ... 4 Clearly, f(z)=\exp\left(\frac{z}{1-z}\right) is analytic in the open unit disk D(0,1). Thus, \forall\,z\in D(0,1),\qquad f(z)=\sum_{n=0}^\infty a_nz^n $$and we are seeking a bound on a_n. Consider r a positive real from (0,1) then, by Cauchy's formula applied to the circle C^+(0,r), we have$$ a_n=\frac{1}{2\pi ... 3 Lets=x(t-1)^n$. We then get$t = 1 + \left(\dfrac{s}x\right)^{1/n}$. We get$dt = \dfrac1{x^{1/n}} \dfrac{s^{1/n-1}}n ds$. Hence, $$I_n(x) = \int_1^2 \ln t \cdot e^{-x(t-1)^n}dt = \int_0^x \ln \left(1+\left(\dfrac{s}x \right)^{1/n}\right) e^{-s} \dfrac1{x^{1/n}} \dfrac{s^{1/n-1}}n ds$$ Hence, $$I_n(x) = \dfrac1{nx^{1/n}} ... 1 I do not know how much this could help you. Suppose you change variable t=z-x; then$$\int \dfrac{\cos t}{t+x}dt=\int \dfrac{\cos (z-x)}{z}dz=\text{Ci}(z) \cos (x)+\text{Si}(z) \sin (x)$$where appear the sine and cosine integrals. So, going back to t and computing the integral, we arrive to$$f(x)=\int_0^{\pi/2} \dfrac{\cos ... 1 If the inner loop runs $$\sqrt n$$ times and outer loop runs n times as you indicated in you comments then you get: $$n\cdot \sqrt n = n^{3/2}$$ Since $$f=O(g)$$ means that your f grows no faster than g, it follows that $$n^{3/2}=O(n^{3/2})$$ i.e. there is a constant C that makes g grow faster than f. 1 "$f = O(g)$" means that for some$c$and some$x_0$,$f(x) \leq c\cdot g(x)$for all$x \geq x_0$. So, if$f_1 = O(g_1)$and$f_2 = O(g_2)$, there are$c_1,c_2$and an$x_0$with $$f_1(x) \leq c_1 g(1) ,\quad f_2(x) \leq c_2g_2(x) \text{ for all x > x_0.}$$ So what, then, can we say about$f_1 \circ f_2$?. We have for every$x > x_0$that$\$ y ...