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
29 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 ...
0
votes
1answer
15 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 ...
1
vote
0answers
31 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 ...
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
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
17 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 ...
0
votes
1answer
27 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 ...
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
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
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
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: ...
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 ...
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 ...
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 ...
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 ...
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
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} ...
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 ...
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 ...
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
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 ...
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 ...
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?
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 ...
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 ...
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$ ...
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 ...
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 ...
1
vote
1answer
31 views

Computational complexity and the big $\mathcal{O}$

I have a question about this Big $\mathcal{O}$ problem. I have the question down $90\%$, but the other $10\%$ isn't getting to me. I will write out the entire question and I'll point out the step, ...
0
votes
0answers
28 views

What is the sign of the generalized Stieltjes constants $\gamma_{k}(a)$?

Recall that the Stieltjes constants $\gamma_{k}$ appear as the coefficients in the regular part of the Laurent expansion of the Riemann zeta function about $s = 1$: $$ \begin{align} \zeta(s) = ...
2
votes
0answers
42 views

Do asymptotically equivalent coefficients survive convolution at least in Θ?

This is a follow-up question to this one where I asked if asymptotic equivalence of coefficients carried over after convolution, resp. why this was not the case. Answerer Daniel Fischer proposed that ...
0
votes
2answers
23 views

Determine whether the function floor(x) is big omega of x

I'm a little confused on what to answer to this: Determine whether the function floor(x) is big omega of x. The above function holds for integers but not for real numbers. According to the definition ...
0
votes
0answers
21 views

Lower bound for a relative of the central binomial coeff

The central binomial coefficients $\binom{2m}{m}$ have g.f. $\frac{1}{\sqrt{1-4z}}$ and lower bound $\frac{4^m}{\sqrt{4m}} \le \binom{2m}{m}$. I'm interested in a related integer series $$T(2m, m) = ...
1
vote
0answers
27 views

Asymptotic behavior of sums of consecutive powers (bivariate)

Are there some (bivariate) closed form formulas for the asymptotic behaviour of the sum: $$\sum_{k=1}^{n} k^d,$$ where $n$ and $d$ are large integers? I am especially interested in a lower bound of ...
2
votes
1answer
104 views

Why does convolution not maintain asymptotic equality of coefficients?

Assume I have four (generating) functions $f$, $f'$, $g$ and $g'$. If that is interesting, we can assume that they all share the same radius of convergence $\rho > 0$. In addition, we know that ...
1
vote
1answer
86 views

Since $2^n = O(2^{n-1})$, does the transitivity of $O$ imply $2^n=O(1)$?

Let us assume that $f(n)=2^{n+1}$, $g(n)=2^n$ be two functions. Now, use limit to find $O(f(n))$: $\lim_{n\to\infty} \dfrac{2^{n+1}}{2^n}=2$. This is not equal to infinity, so the limit exists, hence ...
1
vote
0answers
32 views

Approximations for finite n in limit-based definition of the exponential function

The exponential function can be defined via: $$ e^x = \lim_{n \rightarrow \infty} \left( 1 + \frac{x}{n} \right)^{n} = \lim_{n \rightarrow \infty} g(x; n) $$ In my problem, I actually have the right ...
1
vote
3answers
49 views

Solving a Perturbed Cubic Equation

Consider a cubic equation $(1 + \epsilon)x^3 - 2ax^2 + (a - 3\epsilon)x + 2\epsilon = 0$ where $\epsilon > 0$ and $a \gg 1$. In the limit of $\epsilon \rightarrow 0$, $x(x^2 - 2ax + a) = 0$ so ...
1
vote
0answers
29 views

Question about finite sums and integer recursions.

Let $n$ be a positive integer and let $g(n)$ be a given strictly increasing integer function such that $0<g(n)<n$ for all $n$. Also the sequence $ |g(n) - n|$ is unbounded as $n$ grows. Let ...