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

learn more… | top users | synonyms (1)

2
votes
0answers
22 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
48 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 ...
2
votes
1answer
39 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
56 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
30 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
38 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
77 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
78 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
23 views

Change of Variables in an Asymptotic Big-Oh Situation

I'm looking at the function $cos(x)^n$ as $n$ varies. It appears to be gaussian. The book says it's easy to verify that it is Gaussian: set $x=\omega/\sqrt n$, and then a local expansion yields: ...
0
votes
2answers
39 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 ...
2
votes
2answers
12 views

Vertex Cover - Understanding the bounds

I was reading on wikipedia about the approximations of the Vertex Cover problem and saw that an approximation algorithm with an approximation factor of $\displaystyle 2 - \Theta \left( ...
6
votes
1answer
37 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 ...
8
votes
0answers
163 views

How to estimate $Pr[vr_i=ur_i]$ in the presence of rotations

Suppose we want to compute the probability that for two different random vectors (with elements that are $0$ or $1$), denoted by $v$ and $u$, multiplying them with the rotations of a random vector $r$ ...
1
vote
2answers
60 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
36 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
88 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
62 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} ...
4
votes
1answer
39 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
45 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
64 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
17 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
46 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
1answer
80 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 ...
2
votes
2answers
72 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
18 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
282 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
54 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
33 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
99 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
237 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 ...
4
votes
5answers
151 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
33 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, ...
1
vote
0answers
39 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
47 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
35 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
25 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
28 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 ...
3
votes
1answer
109 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
92 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
40 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
68 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
32 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 ...
1
vote
2answers
50 views

Check my proof: Big O notation

I was asked the following: We are given the functions $f(n)=n^{10\log(n)}$ and $g(n)=(\log (n))^n$. Which of the following statements is true: $f(n)\in\mathcal{O}(g(n))$, $f(n) \in ...
1
vote
0answers
63 views

Long-time asymptotic behaviour of a system of two ODEs

We have the following nonlinear ODE: $$ f' = af-bg -(f+g)^k \bigl(f'(0) +g'(0)\bigr) + f'(0), $$ $$ \bigl(G-T(x)\bigr) g' = -af+bg - g'(0), $$ where $a,b,k,G$ are constants, $f'(0)$ and $g'(0)$ are ...
1
vote
4answers
128 views

Proving Big Oh Notation

Show that $f(n) = n^{2} + 2n + 1$ is $O(n^{2})$. Sorry if this is a duplicate question or anything but I'm terribly having a hard time understanding this big-oh notation. I've looked for methods on ...
1
vote
3answers
71 views

Proving that $f(x)=2^x$ is $O(x^2)$

Can someone help me with this problem? I don't really know what to do if the x is in exponential form.
1
vote
1answer
21 views

Relationship between big O notation and exponential type

Let $f: \mathbb{R} \to \mathbb{R}$, $C\in \mathbb{R}$. What, if any, is the difference between "$ f = O(e^{Cx}) $" and "$f$ is of exponential type $C$"? If they're different, is it possible to ...
2
votes
1answer
88 views

Asymptotic expansion on 3 nonlinear ordinary differential equations

The 3 nonlinear differential equations are as follows \begin{equation} \epsilon \frac{dc}{dt}=\alpha I + \ c (-K_F - K_D-K_N s-K_P(1-q)), \nonumber \end{equation} \begin{equation} \frac{ds}{dt}= ...
1
vote
1answer
51 views

Asymptotic behaviour of a sum

Let $p$ and $q$ be positive real numbers such that $p+q = 1$. am interested in in the large-$n$ behaviour of a following sum: \begin{equation} \sum\limits_{j=0}^{n-1} \left(1 + \frac{n-j-1/2}{j+1} ...