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
26 views

Lower bound on $F$ under the assumption $\theta F(s)\le sF'(s)$

Let $F(s)=\displaystyle \int_0^{s}f(t)\,\mathrm dt$. We suppose that there exists $\theta>2$ such that $\theta F(s)\le f(s)s$ for all $s\in \mathbb{R}$ and that $F(s)>0$ for all ...
11
votes
2answers
539 views

Showing that $\lim_{n\to\infty}\sum^n_{k=1}\frac{1}{k}-\ln(n)=0.5772\ldots$

How to show that $$\lim_{n\to\infty}\left[\sum^n_{k=1}\frac{1}{k}-\ln(n)\right]=0.5772\ldots$$ No clue at all. Need help! Appreciated!
0
votes
1answer
13 views

What's time complexity of algorithm for “Word Break”?

Word Break(Dynamic Programming) Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible ...
4
votes
4answers
166 views

An asymptotic term for a finite sum involving Stirling numbers

The question is a by-product at the end of this post. The following asymptotic term will ensure the convergence of some series. $$ \frac{1}{n!} \sum_{k = 1 }^{n } \frac{{n \brack k}}{k+1} = ...
8
votes
3answers
120 views

Prove that $\prod_{k=1}^{\infty} \big\{(1+\frac1{k})^{k+\frac1{2}}\big/e\big\} = \dfrac{e}{\sqrt{2\pi}}$

This result, $$\prod_{k=1}^{\infty} \big\{\big(1+\frac1{k}\big)^{k+\frac1{2}}\big/e\big\} = \dfrac{e}{\sqrt{2\pi}}$$ is in a paper by Hirschhorn in the current issue of the Fibonacci Quarterly (vol. ...
1
vote
0answers
28 views

Asymptotic behaviour / Convergence

Let $0<\omega<\infty, \mu >0$ and $z \in \mathbb{R}.$ In my book, it is written that we have the following asymptotic behaviour: i) Claim: $$\lim_{t \rightarrow \infty} \frac{z ...
0
votes
0answers
34 views

Can we show this?

Let us assume that we have $x\in \{0,...,x_0\}$. We have $p(x)\geq 0$ for all $x$ and $\sum_{x=0}^{x_0} p(x)=1$. Define $\mu:= \sum_x x p(x) = \omega(1)$. Let $P(x)=1$ iff $x p(x) = ...
1
vote
1answer
52 views

Can I prove this, or hopeless? Deviating too much from mean

Can I prove this: We have a sequence of vectors $\left(X_i(n)\right)$ for $i=1,\ldots,t$, where $n\rightarrow \infty$. $t$ does depend on $n$ and is Chosen such that $1 \ll t \ll n$, for instance, ...
0
votes
0answers
19 views

How to choose the parameter?

Can I choose Parameters $\beta \in (1,2)$ and $1 \ll x \ll n$, such that $$\sum_{i=1}^{x} i i^{-\beta} \gg \sum_{i=x+1}^{n} i i^{-\beta}$$ Would be great if you could give an example.. $\gg$ means ...
0
votes
0answers
29 views

Geometric series: Convergence under which conditions?

For which functions $p(n)$ does $$\sum_{i=0}^{n} i (p(n))^i \rightarrow \infty$$ but $$ \frac{1}{n} \sum_{i=0}^{n} i (p(n))^i \rightarrow 0$$ Or stated differently: I want $$ 1 \ll \sum_{i=0}^{n} i ...
0
votes
0answers
13 views

Simplification of a polynomial before Asymptotic series expansion

I am wondering about a very basic point related to "Asymptotic series expansions". There is a function $f(R)$ which must be expanded as $R$ goes to $ \infty $. Consider that $f(R)=g(R)*p(R)$ where ...
0
votes
1answer
21 views

Show that $\int_{2}^x\frac{\pi(t)}{t(t-1)}dt=\log \log x+ O(1)$

Show that $\int_{2}^x\frac{\pi(t)}{t(t-1)}dt=\log \log x+ O(1)$ Do you use the fact that $\pi(t) = \frac{t}{\log t} + O\left(\frac{t}{\log^2t}\right)$ and then $\int_{2}^x\frac{\pi(t)}{t(t-1)}dt= ...
0
votes
1answer
34 views

How would you show $\pi(x)\log(1-\frac{1}{x}) \sim \frac{1}{\log x}$

How would you show $\pi(x)\log(1-\frac{1}{x}) \sim \frac{1}{\log x}$? Would you use $\lim_{x\to \infty}\frac{\pi(x)\log(1-\frac{1}{x})}{\frac{1}{\log x}} = 1$? and how would you show this? Can you ...
1
vote
0answers
23 views

How to show an aymptotic expansion is uniformly valid?

I have an equation $$ nt = u - \epsilon \sin(u) $$ which asks for the first four terms in the asymptotic solution. Hence if the solution is $u_0 + \epsilon u_1 + \cdots.$, expand $\sin(u)$ around ...
0
votes
0answers
19 views

Approximate $_2F_1(a,b;c;x)$ for large (maybe negative) values of $a, b, c$?

I need asymptotic approximations of the Hypergeometric function $_2F_1(a,b;c;x)$ for large positive values of $a, b, c$. Specifically, I need approximations for all the possible regimes, in which one ...
2
votes
0answers
16 views

Incomplete Beta function $\text{B}_x(\alpha,\beta)$ approximation for large $\alpha,\beta$?

I need good asymptotic approximations to the incomplete Beta function $\text{B}_x(\alpha,\beta)$ for large values of $\alpha,\beta$. Specifically, I need approximations valid for the following ...
3
votes
1answer
72 views

Divisor function asymptotics

Define $\tau_{r}(n) = \sum_{d_1...d_r = n}1$. One exercise in a book on sieve theory asked for an elementary proof by induction of the fact that $$\sum_{n\le x}\tau_r(n) = \frac{1}{(r - 1)!}x(\ln ...
0
votes
1answer
26 views

For which function $f$ is $1 \ll \sum_{i=1}^{n} i \cdot i^{-f(n)} \ll n$?

I am interested in the expected value of a power-law Distribution. I would like to let the Parameter $f(n)$ depend on $n$ for $n \rightarrow \infty$. And now I would like to determine $f(n)$ such ...
-1
votes
1answer
30 views

How do I prove that $a = n/2$ is a tight upper bound for the recurrence relation $T(n) = T(n-a) + T(a) + n$?

I have a recurrence relation: $$T(n) = T(n-a) + T(a) + n$$ which happens to be $O(n^2)$ complexity. How do I now prove that: $$a = n/2$$ is a tight upper bound for this relation? I have been ...
0
votes
0answers
25 views

Closed-form term for this Gaussian expression

Related to this question, I have a random variable $X \sim N(\mu,\sigma)$. I am interested in $P[X \leq k]$ for $k=O(1)$, $\mu =o(1)$, $\sigma \sim \mu$. Is there some function $f$ such that ...
1
vote
1answer
34 views

Closed-form term for this expression

I have a normal Distribution $X \sim N(\mu, \sigma)$. Is there an easy way to give an asymptotic estimate with small error (I would prefer with relative error $\rightarrow 0$) for $P[X \geq k]$? We ...
0
votes
2answers
38 views

How to prove that $n^{1.1} \not\in O(n(\log n)^2)$

This is a problem from a university exam: True or false: $n^{1.1} \in O(n(\log n)^2)$. The solution says False, but I'm unable to prove it. I tried using the limit test for Big-O: $\lim_{n \to ...
2
votes
0answers
73 views

asymptotic expansion of the integral for large tau

How can I proceed to resolve this integral? $$ c_1\int_{-\infty}^{\infty}{\frac{\cos\left(x\tau\right)}{\left(1 + c_{2}\,x\right)^{\alpha}}}\, \,{\rm d}x $$ where $c_1, c_2$ are positive constants, ...
2
votes
1answer
25 views

$f(t) = \cos t^{-1} + \int_t^\infty \frac{1}{\tau^2 + f(\tau)^2} d\tau$ implies the integral is $O(\frac{1}{t})$

The following is a quote from "asymptotic methods in analysis" by de Bruijn (p. 136). If we know that the real function $f(t)$ satisfies the relation $$f(t) = \cos t^{-1} + \int_t^\infty ...
2
votes
1answer
31 views

Difference between $\lim P[…]$ and $P[ \lim ]$

In a Galton-Watson branching process the extinction probability is sometimes given by $$\lim_{t \rightarrow \infty} P[X(t)=0]$$ and sometimes as $$ P[\lim_{t \rightarrow \infty}X(t)=0]$$ Is there a ...
2
votes
2answers
71 views

Growth Rate of Alternating Sign Matrices

I am trying to compute the best growth rate for the following sequence $$ a_n=\prod_{k=0}^{n-1}\frac{(3k+1)!}{(n+k)!} $$ This sequence counts the number of $n\times n$ alternating sign matrices: ...
6
votes
1answer
32 views

Equivalent of a sequence in regard to a certain length of a cycle for $\mathfrak{S}_{n}$

Let $n \in \Bbb{N}$ ( for me $0\notin \Bbb{N})$. Find the limit as $n$ tends to $+ \infty$ of the following sequence $$\frac{\alpha_{n}}{n}$$ where $\alpha_{n}$ is the number of permutations of ...
0
votes
2answers
36 views

Asymptotic behaviour of $\prod_{p \leq x} (1 + 4/(3p) + C p^{-3/2})$

I'm reading Montgomery and Vaughan and in it they state quite simply \begin{equation} \prod_{p \leq x} \left(1 + \frac{4}{3p} + \frac{C}{p^{3/2}} \right) \ll (\log x)^{4/3} \end{equation} as $x ...
0
votes
0answers
15 views

Change of Variables in an Asymptotic Big-Oh Situation

I'm looking at the function $cos(x)^n$ as $n$ varies. I'm told in a book that this tends to conform to a bell-shaped profile, which by inspection it does seem to. Then it says "This is not hard to ...
1
vote
2answers
31 views

Differential Equations: Asymptotic Behavior

I'm new to differential equations, so any help will be grateful. I've been looking at this problem: Examine the slope field of the following differential equation. Based on the direction field, ...
0
votes
1answer
33 views

Inequality with little-o notation

I'm having trouble justifying the following: For large $n$, \begin{align*} -\log f(n) & < \log n + o(\log n)\\ \implies f(n) &> n^{-1} \log^3(n) \log(10) \end{align*} I think basically ...
1
vote
0answers
28 views

What distribution does $Y$ have?

I have given $(X_1, ...,X_{n-1})$ which follow a Multinomial Distribution $\mathrm{Mul}(n, (p_1,...,p_{n-1}))$. Now, how do I model $$Y:=\sum_{i=1}^{n-1}\mathrm{Bin}(X_i, q_i)$$ What is the ...
0
votes
1answer
61 views

Is this possible or hopeless to try to prove?

If I have $x_1, ..., x_k=o(n)$ and $j=O(1)$. Is it possible to prove something like: $$\sum_{i=1}^k {n \choose j} \left(\frac{x_i}{n}\right)^j \left(1-\frac{x_i}{n}\right)^{k-j} \sim {n \choose j} ...
1
vote
1answer
58 views

Asymptotic expansion of $\sum_{n = 2}^{x} \dfrac{1}{\log(n)}$ and $\sum_{n=1}^{x}\dfrac{1}{\sum_{k=1}^{n}k^{-1}}$

Presumably \begin{align} \operatorname{Li}(x) = & \sum_{n = 2}^{x} \dfrac{1}{\log(n)}+ O(\log(x))\\ \end{align} where \begin{align} \operatorname{Li}(x) = & ...
1
vote
1answer
44 views

Find real-valued sequences $x(n)$ for which $c^{x(n)} = o(1/n )$

For which $x=x(n)$ does it hold that $$c^x = o\left(\frac{1}{n}\right)$$ where $c\in(0,1)$ is a constant. So clearly, for $x=n$, this is true. But for which $x =o(n)$ does this hold? I thought ...
6
votes
1answer
32 views

How can I find a $k$ and a $n_0$?

Find $k$ such that $$(\lg n)^{\lg n}= \Theta (n^k), k \geq 2$$ That's what I did so far: $$(\lg n)^{\lg n}=\Theta(n^k) \text{ means that } \exists c_1,c_2>0 \text{ and } n_0 \geq 1 \text{ such ...
2
votes
1answer
56 views

Asymptotics of coefficients $[x^n] \frac{1}{\Gamma(1+x)}$ as $n$ is great

I am interested in the behaviour, as $n$ is great, of the coefficients $g_n$ in the Maclauren expansion of $\displaystyle \frac{1}{\Gamma(1+x)} $. We have $$ \frac{1}{\Gamma(1+x)}=\sum_{n=0}^\infty ...
1
vote
1answer
463 views

Proving that $3n^2 + n \log_2n - 2$ is $\Theta (n^2 - 5n +1)$

Specifically the following: $3n^2 + n \log_2n - 2 \in \Theta (n^2 - 5n +1)$ I'm aware it needs to be $g(n)c_1 \le f(n) \le g(n)c_2$, where $g(n)$ is $\Theta (n^2 - 5n +1)$ and $f(n)$ is $3n^2 + n ...
1
vote
1answer
14 views

Properties of Asymptotic series Expansion

I am wondering about the properties of "Asymptotic series expansion". Considering a representative function $ f(R)=\frac{a+bR+cR^2}{d+eR+fR^2}$ where $ a, b, c , d , e , f $ are constants. How ...
0
votes
2answers
43 views

When $\ln(1+y) = y + o(y)$?

I was reading a proof which utilize the fact that: $\ln(1+y) = y + o(y)$ http://math.stackexchange.com/a/842557/160028 I'm not so sure what is the meaning of $\ln(1+y) = y + o(y)$. When is it ...
3
votes
2answers
70 views

The growth of the solution of the recursive relation $P(n)=\sum_{k=1}^{n-1} P(k) P(n-k)$

According to my notes,one solution of the recursive relation: $$P(n)=\sum_{k=1}^{n-1} P(k) P(n-k), \text{ for } n>1 \\ P(1)=1$$ is $\Omega(2^n) $. How do we conclude that this is one solution?
3
votes
2answers
64 views

How to find an approximate values of rational function $f(x)$ for large $x$, neglecting $\frac{1}{x^4}$ and successive terms?

This is the function that I want to find an approximate value for it neglecting $\displaystyle \frac{1}{x^4}$ and successive terms $$ f(x)=\frac{25x}{(x-2)^2(x^2+1)}. $$
9
votes
4answers
265 views

Asymptotic behavior of $\sum\limits_{k=1}^n \frac{2^k}{k}$

I'm looking for an asymptotic equivalent of $$\sum_{0 < k \le n} \frac{2^k}{k}$$ as $n \to \infty$. A plausible candidate seems to be $\frac{2^{n+1}}{n+1}$ (WolframAlpha plot, and the intuitive ...
0
votes
0answers
15 views

Normalizing Data for Graph

Firstly, sorry for the long post, but I must be detailed in my explanation here. This is a computer science heavy topic, and I've posted it on the CS section of Stack Overflow already, but the main ...
1
vote
0answers
51 views

Definition of $O (.) $ notation

The book I am currently reading defined the big oh operator as the following: A function $ g (x) $ said to be $ O (h (x)) $ as $ x \to l $ if $\lim \sup_{x \to l} |g (x)/h (x)| < \infty $. What I ...
1
vote
1answer
32 views

Clarification: how to get the following asymptotics

I'm having some trouble justifying some steps in a paper. Let $a_n$ be an increasing sequence of integers satisfying $n! \le a_n \le 2(n!)$, and let $f:\mathbb{N} \to \mathbb{N}$ be a function ...
6
votes
1answer
98 views

Some conditions to obtain that $\int_1^{x}e^{f(t)}dt\sim_{x \rightarrow +\infty}\frac{\exp(f(x))}{f'(x)}$

Playing with the function $e^{t^2}$ I conjectured the following result : Let $f\in C^2(\Bbb{R},\Bbb{R})$, assume that : $f'(x)\rightarrow_{x \rightarrow +\infty}+\infty$ ...
4
votes
1answer
89 views

Can the master theorem be applied in this case?

I have to define an asymptotic upper and lower bound of the recursive relation $T(n)=5 T(\frac{n}{5})+\frac{n}{ \lg n}$. I thought that I could use the master theorem,since the recursive relation is ...
5
votes
5answers
148 views

Why is $f(n) =\frac{n(n+1)(n+2)}{(n+3)}$ in $O(n^2)$?

Let: $$f(n) = n(n+1)(n+2)/(n+3)$$ Therefore : $$f∈O(n^2)$$ However, I don't understand how it could be $n^2$, shouldn't it be $n^3$? If I expand the top we get $$n^3 + 3n^2 + 2n$$ and the biggest ...
3
votes
1answer
220 views

Proving that, if a function f is O(g), the ceiling of f is also O(g).

I'm having a bit of trouble with this problem: $$\forall (f, g) \in F, f \in O(g) \implies \lceil{f}\rceil \in O(g)$$ Where F is the family of functions from $\mathbb{N}$ to $\mathbb{R}^+$. I know ...