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

learn more… | top users | synonyms (1)

6
votes
4answers
70 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
30 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
20 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
32 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
22 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
16 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
21 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
97 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
83 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
31 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
47 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
25 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
38 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 ...
0
votes
0answers
30 views

Is it true that $k^{\lceil f(k) \rceil}(1+o(1)) = k ^{f(k)}(1+o(1))$? [on hold]

Is it true that $k^{\lceil f(k) \rceil}(1+o(1)) = k ^{f(k)}(1+o(1))$? I think the answer is no?
1
vote
0answers
44 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
38 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
69 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
11 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
62 views
+50

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
46 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} ...
8
votes
1answer
116 views

Asymptotic Behaviour Of A Bizarre Function 2

It is well-known that $$\frac{1}{1}-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\cdots = \ln 2 $$ Hence $$\frac{x}{1}-\frac{x}{2}+\frac{x}{3}-\frac{x}{4}+\cdots= x\ln 2 $$ However, consider $f(x)$, where ...
1
vote
1answer
59 views

Asymptotic Problem

Let us assume that $f(n)=2^{n+1}$, $g(n)=2^n$ be two functions. Now, using limit to find $\mathcal{O}(f(n))$, $\lim_{n\to\infty} \frac{2^{n+1}}{2^n}$we get 2 as answer 2 is less than infinity, so ...
0
votes
1answer
42 views

Why, or why not, is $5^{log_3(n)} \in \mathcal{O}(n^2)$?

Why, or why not, is $5^{\log_3(n)} \in \mathcal{O}(n^2)$ ? I tried transforming the logarithm to a base of 5, so that the logarithm and power cancel each other out. However, when I try to so I get ...
0
votes
1answer
20 views

Asymptotic notation problems, am i correct??

$f(n)$ belongs to $\Theta(g(n))$ then it implies that $2^{f(n)}$ belongs to $\Theta(2^{g(n)})$. [True] $f(n)$ does not belong to $o(g(n))$ and $f(n)$ does not belong to $\omega(g(n))$ then it ...
7
votes
1answer
194 views

An equivalent for $\int_0^1\left(\frac{1}{\log x}+\frac{1}{1-x}\right)^n\;dx$

Set $$ I_n :=\int_0^1\left(\frac{1}{\log x} + \frac{1}{1-x}\right)^n \:\mathrm{d}x \qquad n=1,2,3,.... $$ We have $$I_1 =\gamma, \quad I_2 =\log (2 \pi) - \frac 32, \quad I_3 = 6 \log A - ...
5
votes
1answer
32 views

Asymptotics bound on Jacobi polynomials in the complex plane and for large $n$

Dear mathematicians and theoretical physicists, I am a theoretical physicist and I am bothering to you since I need to know some asymptotic and analytical properties of Jacobi polynomials ...
1
vote
3answers
44 views

Finding Horizontal/Oblique Asymptote of $y=\frac{\sqrt{x}+1}{\sqrt{x}-1}$

Is it correct to simply subsitute $\sqrt{x}$ with $x$ when finding horizontal or oblique asymptotes? The method works but I am not sure if it is formally sound enough to pass muster in an examination. ...
5
votes
2answers
90 views

How is $ \sum_{n=1}^{\infty}\left(\psi(\alpha n)-\log(\alpha n)+\frac{1}{2\alpha n}\right)$ when $\alpha$ is great?

Let $\psi := \Gamma'/\Gamma$ denote the digamma function. Could you find, as $\alpha$ tends to $+\infty$, an equivalent term for the following series? $$ \sum_{n=1}^{\infty} \left( \psi (\alpha ...
4
votes
3answers
50 views

Show that $\frac{x^4 +7x^3+5}{4x+1}$ is big-theta($x^3$)

I'm having trouble grasping how to set these types of problems. There are a lot of related questions but it's difficult to abstract a general procedure on finding constants that give the given ...
2
votes
1answer
54 views

Prove that limits can be used for asymptotic analysis

True or false: If f(n)=$\Theta$(g(n)), then $$\lim_{n\rightarrow \infty}\frac{f(n)}{g(n)}$$ exists and is equal to some real number. I'm not sure what needs to be done to demonstrate this. I do ...
1
vote
0answers
26 views

What is the power series for a half-exponential function?

What is the power series of a half-exponential function? Half-exponential means that $f(f(x)) = y^x, y > 1$
4
votes
2answers
68 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} = ...
0
votes
0answers
21 views

Power iteration sequemce for a special nonnegative irreducible imprimitive matrix

Let $A \in \mathbb{R}^{n \times n}$ be nonnegative irreducible matrix with maximum positive eigenvalue equal to 1. Let's assume $A$ has $h$, $h > 1$ eigenvalues $\lambda_1, \dots, \lambda_h$ with ...
4
votes
1answer
66 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 ...
0
votes
1answer
36 views

Show that $Pr[X \gg Y]\approx 1$

Can one show (and how) that $$Pr[X \gg Y]\approx 1$$ for $$X:=\sum_{i=1}^k Bin\left(n\left(\frac{1}{2}\right)^i,i\right)$$ and $$Y:=\sum_{i=k+1}^{\infty} ...
0
votes
0answers
63 views

Prove $Pr[X + Y \geq x] \sim Pr[X \geq x]$

We have two independent random variables $X_n$ and $Y_n$, where $$X_n=\sum_{i=0}^n x_i$$ and $$Y_n=\sum_{j=0}^n y_j,$$ where $x_i$,$y_j$ are (non-identically) Bernoulli distributed and independent. ...
1
vote
0answers
20 views

How can I show that $T(n) \leq c_2 n \lg n$?

I have to define an asymptotic upper and lower bound of the recursive relation $T(n)=3 T(\frac{n}{3}+5)+\frac{n}{2}$. Firstly,I solved the recursive relation: $T'(n)=3 ...
1
vote
2answers
37 views

Does $E[X]\gg E[Y]$ for independent RV imply that $Pr[X+Y \geq x] \sim Pr[ X \geq x]$?

We have two independent random variables $X$ and $Y$, where we know that $E[X]\gg E[Y]$, thus $\frac{E[Y]}{E[X]}\rightarrow 0$. I am now interested in $Pr[X+Y \geq x]$ and would like to show that ...
1
vote
1answer
41 views

Poisson approximation of $X$ by $Poisson(E[X])$

I've tried to find something, but couldn't find anything about the following question. Is it possible to approximate any random variable $X$ with $E[X]=o(1)$ by a Poisson random variable ...
3
votes
1answer
37 views

Combinatorial identity involving sum of products?

Let $(c_1, c_2, \cdots)$ be an $m$-periodic sequence of natural numbers and let $n$ and $k$ be integers with $0\leq k \leq n$. I am trying to simplify $$ \sum_{\substack{I \subseteq \{1, \cdots, n\}\\ ...
0
votes
0answers
18 views

Vanishes of second order

I encountered the following statement in an article: Let $f(X) = f(X_1, ..., X_N) = \sum_{|\alpha| \geq 2} {a_{\alpha}X^{\alpha}}$ be a convergent power series which vanishes of second order at ...
-3
votes
2answers
88 views

A function that increases faster than $\ln(x)$ when $x$ is small and then slower than $\ln(x)$ when $x$ is big.

As the title indicate: I am looking for a function that increases faster than $\ln(x)$ when $x$ is small and then slower than $\ln(x)$ when $x$ is big. Here is the fig: The red curve is the ...
10
votes
3answers
185 views

Is there a function such that $f(f(n)) = 2^n$?

In this question, I was looking for a specific "middle family" of functions between polynomials and "anti-polynomial exponentials", as I will call them, which are functions like like $2^{\sqrt{n}}$ ...
4
votes
0answers
42 views

Singularities at roots of unity

I want to construct a function $f$ with the following properties: $f$ has a singularity at $z=1$, and for any $\zeta = e^{2\pi i\frac{a}{b}}$ with $(a,b)=1$, then $$\lim\limits_{x\to1^-}\frac{f(\zeta ...
0
votes
0answers
46 views

Little o notation inequalities involving $n^{\log n}$

Apologies as this is a minor re-post, but I didn't think the other would get answers as it diverged into a discussion and got pushed down... I'm struggling with asymptotic notation a little bit... ...
6
votes
0answers
180 views

Entropy of matrix vector product

Consider a random $n$ by $n$ circulant matrix $M$ whose entries are chosen independently and uniformly from $\{0,1\}$. Let $M'$ be the $m$ by $n$ matrix which is formed by taking the first $m$ rows of ...
3
votes
0answers
25 views

How can I show that the solution of the recursive realtion is $O(n \lg n)$?

Show that the solution of the recursive relation $T(n)=2T( \lfloor \frac{n}{2} \rfloor +17)+n$ is $O(n \lg{n})$. I am supposed to use the substitution method.. That's what I have tried: Let ...
0
votes
0answers
89 views

Please give me an example of the algorithm where $\Theta$ will be equal to $e^n$

Please give me an example of the algorithm where $\Theta$ or $O$ will be equal exactly to $e^n$ . The algorithm should not be simple counting from 0 till $e^n$ . It should be a clear relation of two ...
0
votes
0answers
23 views

relative error of Poisson approximation to sum of Binomial

We have given $X_i\sim Bin(n_i,p_i)$ for $i \in \{1,...,m\}$ and are interested in $$P[X \geq x]$$ for $X=\sum_{i} X_i$. As we can approximate $X_i$ by $Y_i \sim Poisson(n_i p_i)$, I wonder, ...
2
votes
0answers
61 views

Interchanging limits with the prime counting function

How does one justify that $$\lim_{s \to 1} \lim_{x \to \infty} \frac{\pi(x)}{x^s} = \lim_{x \to \infty} \lim_{s \to 1} \frac{\pi(x)}{x^s}, \quad s > 1,$$ without using the fact that the primes have ...