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
1answer
18 views

Relation involving little-o.

I am trying to show that the following relation holds: \begin{equation} \log(1+ax) = log(x) + o(log(x)) \end{equation} as $x\rightarrow \infty$, where $a$ a positive number. I tried using Taylor ...
0
votes
1answer
26 views

Leading order of behavior of nth derivative of Gamma function evaluated at x=1 as n approaches infinity

I'm working from Bender and Orszag's "Advanced Mathematical Methods for Scientists and Engineers: Asymptotic Methods and Perturbation Theory" and I am trying to solve problem 6.48(b): Find the ...
1
vote
3answers
79 views

Limit as $n$ goes to infinity of $n^22^n/n!$ [closed]

I have read in a book that $( n^2 2^n)$ is superior to n! this means that the limit below will at least be a constant and $n! = O( n^2 2^n )$, but l could not manage to find it, any ideas ...
2
votes
1answer
63 views

Method of matched asymptotic expansions with Van Dyke

Consider the boundary value problem $$\varepsilon \frac{d^2y}{dx^2}+(1+x)\frac{dy}{dx}+y=0$$ subject to $y(0)=0$, $y(1)=1$, for $0 \leq x \leq 1$. Use the method of matched asymptotic expansions to ...
1
vote
1answer
20 views

Understanding the “vertical shift” property of big Oh

So I have difficulty understanding the big Oh property that says that if $\epsilon$ is some constant and $\epsilon < f$ on a neighborhood of infinity, then $\alpha + f = \mathcal{O}(f) $ . I have ...
2
votes
1answer
102 views

In the limit of $N \rightarrow \infty$, find solution $z$ to $\text{e}^{-(z+N)} \sum \limits_{k=0}^{N} \frac{(z+N)^k}{k!}=\frac{1}{2}$

Fix an integer $N$, and consider the unique positive solution $z$ to the following equation: $$\text{e}^{-(z+N)} \sum \limits_{k=0}^{N} \frac{(z+N)^k}{k!}=\frac{1}{2}$$ For $N = 0$, we find that $z ...
0
votes
1answer
25 views

is $O(3^k)$ polynomial for $k\in o(n)$?

For variable $n\in \mathbb{N}$, $O(3^n)$ is certainly an exponential, fix any integer $k\in o(n)$, is the function $O(3^k)$ polynomial ? If not when is it possible for $O(3^k)$ to become polynomial ...
0
votes
0answers
37 views

An aquidistributed sequence

Prove that $\{an^\sigma\}$ is equidistributed in $ [0,1) $,if $\sigma>0$ is noninteger and $a\neq 0$. I know how to solve this problem if $\sigma <1$ , so it is not a duplicate of ...
0
votes
2answers
47 views

Why does for $f(n)\sim n^{-1/3}$ we have $g(n) \equiv [f(n)]^2 = O(n^{-2/3}) = o(n^{-1/2})$ as $n\to\infty$ for $n\geq 1$?

Using the definition we have $$n^{2/3}g(n)\leq C<+\infty$$ On the other hand $$\lim_{n\to\infty}n^{1/2}g(n)=0$$
3
votes
3answers
55 views

Asymptotic Equivalence $e^{x^2+x} \sim e^{x^2}$?

I've a doubt regarding the asymptotic equivalence of two functions. From the definition $f(x)\sim_{x\to x_0} g(x) \iff \lim_{x\to x_0} \frac{f(x)}{g(x)} =1$ While I was trying to determine the ...
2
votes
2answers
48 views

Exact solution of Second order ODE

We have the second order differential equation $\epsilon \dfrac{d^{2}y}{dx^{2}} + \dfrac{dy}{dx} +y = 0$ with boundary values $y(0)=0,\, \, \, y(1)=1$. I would like to get the exact solution in ...
5
votes
2answers
234 views

The integral $\int\ln(x-\ln(x))~dx$

The integral $f(y)=\int_0^y\ln(x-\ln(x))~dx$ is on my mind. I'm not sure if this has a closed form? Maybe we need to use the lambert-W function to solve this one? If it cannot be done in closed ...
8
votes
4answers
222 views

A disease spreading through a triangular population

I have run into this problem in my research, which I'm presenting under a different guise to avoid going into unnecessary background. Consider a population that is connected in a triangular manner, ...
3
votes
0answers
46 views

Which version of Taylor Theorem is this?

Suppose $X$ is a random variable and $\psi(t)=E[\exp(itX)]$ is its characteristic function. Let $K(t)$ be the principal value of the logarithm of $\psi(t)$. Suppose further that ...
0
votes
0answers
17 views

Relation between existence of moments and Big O notation

Consider a sequence of real-valued random variables $\{X\}_{n \in \mathbb{N}}$. Could you help me to clarify the relation (if any) between the following two assumptions: 1) $|E(X_n^p)|<\infty$ for ...
0
votes
1answer
34 views

Relation limsup, liminf, lim

Consider a sequence of real numbers $\{X_n\}_{n \in \mathbb{N}}$ and suppose that I have shown that $\forall \epsilon>0$, $\limsup_{n\rightarrow \infty} X_n-X\leq\epsilon$ and ...
1
vote
3answers
49 views

“Good approximation” for the inverse function of $y = x\log_2 x, \hspace{2mm}x>1 $?

I encountered to solve $x$ from $y$ in the equation $y = x\log_2 x ,\hspace{2mm} x>1$, which is known to have no closed form for its inverse function ...
2
votes
1answer
68 views

What is happening in this integration?

I found in Peskin-Schroeder, while reading Quantum Field Theory. the following integration. $$\frac{1}{4\pi^2 r}\int_m^\infty \frac{se^{-sr}}{\sqrt{s^2-m^2}} = e^{-mr}$$ at the limit $r \rightarrow ...
2
votes
1answer
159 views

Asymptotic value of permutations of general Rubik Cube

I found this on C|NET, and wondering if there was anything like a $1000\times1000\times1000$ cube? And how many arrangements would it have? Or if this is too much, how about an asymptotic formula for ...
2
votes
0answers
41 views

Bounds on twin prime counting function

I read somewhere (unfortunately I cannot find the paper again) that the twin prime counting function $\pi_2(x)$ satisfies $\pi_2(x) \leq C\frac{x}{\log^2x}$ for some constant $C$. How would one prove ...
6
votes
1answer
185 views

Estimating $\int_e^x \log\log{t}\, dt$ so the error term in within $O\left(\frac{x}{\log^2{x}}\right)$

How can one estimate the integral $$\int_e^x \log\log{t}\, dt$$ so that the error term is within $O\left(\frac{x}{\log^2x}\right)$? We may assume that $x>e$. Any hint?
2
votes
1answer
26 views

Big O: Trouble finding Witnesses

I am trying to follow this example but I am stumped by where numbers are coming from: Show that $f (x) = x^2 + 2x + 1 $ is $O(x^2). $ The solution is as follows: We observe that we can readily ...
3
votes
1answer
59 views

Evaluation or asymptotic for $\int_1^x y\sin\left(\frac{2\pi (y-1) x}{y}\right)dy$

Truly, my genuine problem (see Appendix for context) is compute in a closed form or an asymptotic, for real $x\geq 1$, for $$\int_1^x\left(\int_0^{y-1}\cos\left(\frac{2\pi t ...
1
vote
1answer
35 views

Time Complexity of Sorting Algorithm

Here's my question: Analyze the runtime of the following algorithm. Will it successfully sort array S of n elements with values from 0 to m-1? ...
4
votes
1answer
70 views

Decreasing by $\sqrt{n}$ every time

We start with a number $n>1$. Every time, when we have a number $t$ left, we replace it by $t-\sqrt{t}$. How many times (asymptotically, in terms of $n$) do we need to do this until our number gets ...
12
votes
4answers
221 views

An equivalent for $\sum_{n=0}^{\infty} e^{-x\sqrt{n}}$ as $x$ tends to $0^+$

I would like to obtain an equivalent form for $$ f(x)=\sum_{n=0}^{\infty} e^{-x\sqrt{n}} $$ as $x \rightarrow 0^+$. I tried without success to "remove" the $\sqrt{\cdot}$ in the summand by summing ...
5
votes
0answers
88 views

On the change $u=x^{1+\frac{1}{p_n}}$ in $\log \zeta(s)=s\int_0^\infty\frac{\pi(x)}{x(x^s-1)}dx$, where $p_n$ is the nth prime number

In [1] Wikipedia say that for $\Re s>1$ the Riemann zeta function satisfies $$\log \zeta(s)=s\int_0^\infty\frac{\pi(x)}{x(x^s-1)}dx,$$ where $\pi(x)$ is the prime counting function, and say too ...
0
votes
0answers
11 views

Second and higher order asymptotic approximation to statistics

I have been studying the asymptotic approximation to statistics and it seems that most of the expansions are of the form $\sqrt n (\hat{\theta}-\theta_0)=n^{-1/2}\sum M(\theta_0)+o_p(1)$, which I ...
0
votes
0answers
37 views

Obtaining a good asymptotic of a logarithmic sum

Consider the $n$-tuples $k:=(k_{1},...,k_{n})$ of non-negative integer-valued vectors. Define $s:=|k|:=k_{1}+k_{2}+...+k_{n}$. Let $\gamma_{s}:=\frac{s^{n+1}}{(n-1)!(n+1)}.$ Let us take $n=2.$ I ...
1
vote
1answer
27 views

Two functions with the same asymptotic power series, and its notation

consider two functions $f,g:(0,1)\rightarrow\mathbb{R}$ which have the same asymptotic power series for $t\downarrow 0$, i.e. $f(t)\sim\sum_k a_k t^{k}$ and $g(t)\sim\sum_k a_k t^{k}$ as $t\downarrow ...
0
votes
0answers
10 views

Asymptotic behavior of reordered double sequence

Let $$ a_{j,k}=(1/c)^{sj},\qquad k=1,\dotsc,c^{tj} $$ with some fixed $(1<)c$, $(0<)s,t$. Consider reordering $a_{j,k}$ following the lexicographic order, and let the resulting sequence be ...
0
votes
0answers
10 views

Two-Step Estimation: Rigorously show that the asymptotic distribution of $\theta$ does not relect the error in the first step estimation.

Consider any two step estimator s.t. $\hat{\theta} \rightarrow_p \theta_0$ at the second step even when $\gamma$ is held fixed at some value $\underline{\gamma} \neq \gamma_0$ at the second step, ...
1
vote
2answers
164 views

Treating the little-o-notation as a quantity?

I understand that for two functions $f(n)$ and $g(n)$ for $n\in\mathbb N$, the notation $$g(n)=o(f(n)) \mbox{ as } n\rightarrow \infty$$ means that for all $\epsilon>0$, there exists $N\in\mathbb ...
18
votes
8answers
4k views

Stirling's formula: proof?

Suppose we want to show that $$ n! \sim \sqrt{2 \pi} n^{n+(1/2)}e^{-n}$$ Instead we could show that $$\lim_{n \to \infty} \frac{n!}{n^{n+(1/2)}e^{-n}} = C$$ where $C$ is a constant. Maybe $C = ...
1
vote
1answer
23 views

Disproving big $O$ identity

How can I disprove that $2^{(n^2)}=O(2^n)$? Should I show that $\forall c >0$ we have $2^{n^2}>c\cdot 2^n$?
1
vote
1answer
12 views

Asymptotic lower bound for R(k,k)

I'm reading Spencer's lectures on the probabilistic method. Using the Lovasz local lemma, we've shown that $R(k,k)>n$ if $$ 4{k \choose 2} {n \choose k-2} 2^{1-{k \choose 2}} < 1. $$ Now I'm ...
0
votes
1answer
20 views

Does there exist $f$ such that $f(n)=\Omega(\log n)$ and $(f(n))^2=O(f(n))$?

I have to prove/disprove the next 2 statements. I've succeeded with the second, not with the first. There exists $f$ such that $f(n)=\Omega(\log n)$ and $(f(n))^2=O(f(n))$. If $f$ and $g$ are ...
1
vote
1answer
17 views

Prove about big O

I need to prove that: for every $$d>0,\ \epsilon>0,\ n^d=O((1+\epsilon)^n)$$ I'm trying to use the definition: $$n^d\leq c*(1+\epsilon)^n$$ but I don't know how to continue, maybe it is wrong. ...
1
vote
0answers
32 views

How to find asymptotic sum of highly oscillatory series?

I have a sum given by, $$(1) \quad | S_w=\sum_{n=1}^{w} 3^{n/2} \cdot \sin(3^n \cdot t) |$$ How do I find the value of $(1)$ asymptotically? I can guess, using knowledge about the fractal dimension ...
0
votes
1answer
16 views

How big the maximal decrease in consecutive elements of a sequence?

Consider a sequence $(s_1, ..., s_k)$, and we have it sorted in decreasing order $(\tilde{s}_1, ..., \tilde{s}_k)= (\sigma(s_1), ..., \sigma(s_k))$. Define $k_{\max} = \max \left( \max_i \left( s_i ...
0
votes
0answers
21 views

Asymptotic upper bound of a function given by recurrence relation

Can anyone help to understand how to solve this problem? What is the asymptotic upper bound of a function given by recurrence relation: T(n) = T(n / 2) + 1 a. O(n) b. O(lg n) c. O(n lg n) d. ...
0
votes
1answer
46 views

Asymptotic value of a Cauchy Singular integral

Let, $\zeta(x,t) = A_0sin(k_0x)cos(\omega t) + \frac{2k_0A_0}{\pi} \{\int_{0}^{\infty}\frac{cos(kx)cos(\beta t)-cos(k_0x)cos(\omega t)}{k^2-k_0^2}dk\}$ Here $\beta ^2 = gktanh(kh)\ and\ \omega^2 = ...
1
vote
1answer
26 views

What's the order class of T(n) = n(T(n−1) + n) with T(1)=1?

This recurrence basically comes from the typical solution to N-queens problem. Some people say the complexity is O(n) while giving recurrence ...
0
votes
2answers
28 views

comparing functions in big O notation

I am extremely new a calculating big O notation and I am extremely confused by this quote from the book Discrete Mathematics and Its Applications For instance, if we have two algorithms for solving ...
0
votes
1answer
62 views

Using the master theorem to find an upper bound for $T$, where $T(x) \leq 4 T(\left \lfloor{\frac{x}{2}} \right \rfloor) + x$

Let $x \in \mathbb{N}$. We have the relation: $T(x) \leq 4 T(\left \lfloor{\frac{x}{2}} \right \rfloor) + x$. I am trying to find an upper bound for $T$. if $x$ is a power of $2$ i.e. $x = 2^n$. I ...
7
votes
5answers
4k views

Simple proof of showing the Harmonic number $H_n = \Theta (\log n)$

Consider the partial sum of the divergent Harmonic series $H_n = \sum\limits_{k = 1}^{n}\frac{1}{k}$. I recently saw a question which required finding out the asymptotic bounds of $H_n$. Now, I could ...
0
votes
1answer
20 views

Asymptotic complexity of power of logs

I'm trying to simplify $\Theta(lg^k(n/2))$. I believe it's $\Theta(lg^kn)$ but i don't know if the following proof is correct... i'd love to receive some input I tried doing - ...
2
votes
1answer
41 views

If $\lim_{n\to\infty}\frac{\ell_n}{\log n}=1$, does $n\log n\geq -C \iff (n+1)\ell_{n-1}\geq -C$ hold? [closed]

Let $\ell_n:=\sum_{k=0}^{n}\frac{1}{k+1}.$ It is known that $\ell_n\sim\log n.$ i.e $\lim_{n\to\infty}\frac{\ell_n}{\log n}=1.$ Then, for $C\geq 0$ it is possible that $n\log n\geq -C \iff ...
3
votes
2answers
47 views

Asymptotic complexity of sum of poly-logarithmic functions

I'm trying to figure out what's the asymptotic complexity for the following sums: $$\sum_{k=1}^n lg^s k$$ $$\sum_{k=1}^n k^rlg^s k$$ s and r are positive constants. I think i should be using ...
0
votes
0answers
15 views

Are integrals over sequences of functions asymptotic equivalent?

i have given a sequence of functions $(f_{n}(x))_{n>0} $ for which the following holds pointwise : $ \lim_{n \to \infty} \frac{f_{n}(x)}{g_{n}(x)}=1$. Does then also hold: $\lim _{n \to \infty} ...