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

learn more… | top users | synonyms (1)

4
votes
1answer
32 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 ...
10
votes
1answer
251 views

Packing an infinite sequence of disks

Let $a > 1$ and $Q(a)$ denote the supremum of values of $q$ such that a countably infinite collection of disks, whose areas form an infinitely decreasing geometric progression with the start value ...
6
votes
3answers
2k views

how to solve the recurrence $T(n) = 2T(n/3) + n\log n$

How do we solve the recurrence $T(n) = 2T(n/3) + n\log n$? Also, is it possible to solve this recurrence by the Master method?
4
votes
3answers
32 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
52 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
59 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} = ...
2
votes
1answer
66 views

asymptotic behaviour of coefficients in nonnegative matrix iteration

Let $A$ be a square matrix with nonnegative integer coefficients. Is there a simple way to prove that there is a "period" $d$ such that for all $0\leq r<d$, the coefficient $a_{i,j,n}$ at position ...
0
votes
0answers
18 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
34 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
36 views

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

We have two independent random variables $X$ and $Y$, where $X=\sum_{i} X_i$ and $Y=\sum_j Y_j$, where $X_i$,$Y_j$ are (non-identically) Bernoulli distributed and independent. Under the assumption ...
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
34 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
38 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 ...
7
votes
3answers
253 views

How to evaluate $\sum\limits_{k=0}^{n} \sqrt{\binom{n}{k}} $

Can we find $$ \sum_{k=0}^{n} \sqrt{\binom{n}{k}} \quad$$ This problem asked me my friend about a year ago, but I didn't know how to attack problem. Now, I am interesting in solution. Any suggestion? ...
3
votes
1answer
35 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\}\\ ...
2
votes
0answers
98 views
+150

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 ...
0
votes
0answers
17 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 ...
1
vote
1answer
28 views

Proving an asymptotic run time is faster than another using L’Hôpital’s

I'm working on a problem: Show using L’Hôpital’s Rule that a running time of $n\log(n)$ is asymptotically faster than (i.e., little-oh of) a running time of $\frac{n^2}{\log(n)}$.` I suppose a ...
-3
votes
2answers
86 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 ...
-1
votes
0answers
12 views

Let $X_n(s)=o_p(1),\forall s$. Can we infer that $\|X_n\|=o_p(1)$? [closed]

Let $X_n(s)=o_p(1),\forall s$ where $X_n(s)$ is a sequence of random functions. Can we infer that $\|X_n\|=o_p(1)$ where $\|.\|$ is a norm of function $f(s)$?
10
votes
3answers
183 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}}$ ...
0
votes
0answers
41 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... ...
3
votes
0answers
38 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
86 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 ...
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
22 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, ...
-1
votes
0answers
19 views

Asymptotic Notation of polynomials [closed]

If ${P(n)=\sum_{i = 0}^{i=d} a_in^i}$ , where $a_d>0$ be degree-d polynomial in n and let k be a constant. How to proof: If $k>=d$ then $p(n)=O(n^k)$ also $k=<d$ then $p(n)=\Omega(n^k)$ ...
6
votes
1answer
45 views

Prove or disapprove the statement: $f(n)=\Theta(f(\frac{n}{2}))$

Prove or disapprove the statement: $$f(n)=\Theta(f(\frac{n}{2}))$$ where $f$ is an asymptotically positive function. I have thought the following: Let $f(n)=\Theta(f(\frac{n}{2}))$.Then $\exists ...
0
votes
1answer
29 views

Prove or disapprove the statement: $f(n)=O(g(n)) \Rightarrow 2^{f(n)}=O(2^{g(n)})$

Let $f(n)$ and $g(n)$ be asymptotically positive functions. Prove or disapprove the statement: $$f(n)=O(g(n)) \Rightarrow 2^{f(n)}=O(2^{g(n)})$$ That's what I have tried: $$f(n)=O(g(n)), \text{ so ...
1
vote
1answer
20 views

Check if $f(n)+g(n)=O(\min \{ f(n), g(n) \})$

Let $f(n)$ and $g(n)$ be asymptotically positive functions. I want to check if $f(n)+g(n)=O(\min \{ f(n), g(n) \})$. That's what I have tried: Let $f(n)+g(n)=O(\min \{ f(n), g(n) \})$. Then, ...
5
votes
2answers
28 views

Two functions whose order can't be equated - big O notation

Our teacher talked today in the class about big O notation, and about order relations. she mentioned that the set of order of magnitude, is not linear Meaning, there are function $f,g$ such that $f$ ...
3
votes
1answer
40 views

Arrange the functions… [closed]

Arrange in increasing order the following functions: $$n^2 , n! , \lg n , (\frac{3}{2})^n , e^n , n \lg n , 1, (\lg n)^2, 2^{2n}=4^n$$ Could you give me a hint how to do this?
2
votes
0answers
30 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 ...
22
votes
1answer
385 views

Zombie outbreak on a $k$-regular graph

Suppose we have a zombie outbreak on a connected $k$-regular graph of order $n$. There are $n_0$ initially infected zombie nodes, and each turn, each zombie infects its neighbors with probability ...
3
votes
1answer
68 views

asymptotical behavior of integral

I'm interest in the asymptotical of $$\int_{-\pi}^{\pi}\exp\Big((\cos z+i\alpha\sin z-1)t\Big)dz\hspace{3mm}\text{as}\hspace{2mm}t\to\infty$$ for $-1<\alpha<1$. Numberical result suggest that ...
2
votes
3answers
397 views

Polynomial bounds?

Q1: Is the function $$\lceil{\lg n}\rceil!$$ polynomial bounded? Q2: Is the function $$\lceil{\lg\lg n}\rceil!$$ polynomially bounded? $$\lg = \log_2$$ Polynomially bounded: $f(n)$ is polynomially ...
0
votes
1answer
48 views

Are these asymptotic inequalities identical? [duplicate]

I'm struggling with asymptotic notation a little bit... As $k$ becomes large, are these two inequalities actually the same? $k \le n^{\log (n+1) - 1}(1+o(1))$ and $k \le n^{\log (n)}(1+o(1))$? the ...
1
vote
0answers
14 views

asymptotic approximation for number of partitions of integer that do contain 1 nor 2

Hardy and Ramanujan provided a famous asymptotic approximation to $P(n)$ the number of partitions of an integer $n$ when $n$ gets large. I wonder if there is an asymptotic approximation to ...
1
vote
2answers
41 views

How to find the asymptotic behavior of these sums?

Let $$X(n) = \displaystyle\sum_{k=1}^{n}\dfrac{1}{k}.$$ $$Y(n) = \displaystyle\sum_{k=1}^{n}k^{1/k}.$$ $$Z(n) = \displaystyle\sum_{k=1}^{n}k^{k}.$$ For the first, I don't have a formal proof but I ...
0
votes
1answer
22 views

asymptotic notation rearrangment

I'm having a look at this paper http://arxiv-web3.library.cornell.edu/pdf/0903.3048v1.pdf namely Theorem 5 and why it implies Theorem 2 immediately. Basically, I'm hoping somebody could explain to ...
2
votes
0answers
18 views

Is $\frac{x^2(1-p)}{(n-x+1)p}\leq \frac{x^2}{(n-x)p}=O((np)^{-1})=o(1)$?

Is it true that for $n \rightarrow \infty$, $p \gg n^{-1}$, $0<p<1$ and $x=O(1)$, $$\frac{x^2(1-p)}{(n-x+1)p}\leq \frac{x^2}{(n-x)p}=O((np)^{-1})=o(1)?$$
3
votes
1answer
19 views

Big-Theta:What happens if $\displaystyle{a_d<0}$?

If $\displaystyle{f(n)=an^2+bn+c}$ with $\displaystyle{a>0}$ then $\displaystyle{f(n)=\Theta{(n^2)}}$. Generally, if $\displaystyle{f(n)=\sum_{i=0}^{d}a_in^i}$ with $\displaystyle{a_d>0}$ then ...
4
votes
2answers
41 views

Show that $\frac{1}{2}n^2-3n=\Theta{(n^2)}$

Show that $$\frac{1}{2}n^2-3n=\Theta{(n^2)}$$ $$$$ $\displaystyle{\frac{1}{2}n^2-3n=\Theta{(n^2)}: \\ \exists c_1, c_2 >0 , \ \ \exists n_0 \geq 1 \text{ such that } \forall n \geq n_0 \\ ...
2
votes
0answers
41 views

perturbation theory solution of forced Duffing's equation

Question: Find the leading order of the asymptotic expansion for large t: $\frac{d^2x}{dt}+\varepsilon\beta\frac{dx}{dt}+x+\varepsilon x^3=Fcos(\frac{1}{3}\big(1+\varepsilon\omega)t\big)$ I have ...
6
votes
3answers
137 views

Asymptotic behaviour of the integral of the quadratic mean of the coordinates on the hypercube

I have to compute the limit $\lim_{n\to +\infty}I_n$, where: $$\qquad I_n=\int_{[0,1]^n}\sqrt{\frac{1}{n}\sum_{i=1}^n x_i^2}\,d\mu.$$ I believe that its value is just $\frac{1}{\sqrt{3}}$, since the ...
4
votes
1answer
46 views

Examples of sub-exponential functions that aren't exponential functions when chained by a polynomial

Wikipedia talks about two groups of functions with asymptotic growth rates between polynomial and exponential – quasi-polynomial functions and sub-exponential functions. It only gives two ...
0
votes
0answers
50 views

Help inequality with $O(\cdot)$ and $\Omega(\cdot)$

Suppose,$$f(T)\le O\left(\sqrt{\dfrac{\log( T/\delta)}{T}}\right).$$ If we let $\delta=\dfrac{1}{n^2}$ and $T\ge\Omega\left(n^2\log n\right)$, then: $$f(T)\le \dfrac{1}{n}.$$ Can anyone ...
0
votes
2answers
55 views

Sum of independent Bernoulli variables with parameter p which is also a random variable

I've read all the questions related to this, but I couldn't find an answer. We have n independent Bernoulli variables $X_i \in Be(p_i)$ where all the $p_i$ have the same distribution, let's say ...