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

learn more… | top users | synonyms (1)

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. ...
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?
3
votes
3answers
55 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
63 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
28 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$
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
26 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 ...
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} ...
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
42 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
273 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
38 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\}\\ ...
7
votes
0answers
207 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 ...
0
votes
0answers
21 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
39 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
99 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
192 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
55 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... ...
5
votes
0answers
49 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
95 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 ...
1
vote
0answers
30 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
30 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, ...
5
votes
1answer
74 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
45 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
votes
1answer
24 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
36 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$ ...
0
votes
1answer
44 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
158 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 ...
23
votes
1answer
425 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
79 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
458 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
56 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
17 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
43 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
31 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)?$$
1
vote
1answer
20 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 ...
2
votes
2answers
54 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
50 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
147 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 ...
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
61 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 ...
1
vote
1answer
66 views

Meaning of $\sim$?

I often read $f(x) \sim g(x)$ and I wonder what the Standard Interpretation of this $\sim$ is. It seems to mean something like asymptotically equally distributed, something like $f(x)=g(x)(1+o(1))$. ...
4
votes
1answer
112 views

Asymptotic expansion of $\int\limits_0^{\pi / 2} {e^{ix\cos t}}dt$

Using the method of stationary phase, I was able to obtain the first term of the asymptotic expansion of the following integral, as $x \rightarrow \infty$: $$\int\limits_0^{\pi / 2} {e^{ix\cos t}}dt ...
2
votes
1answer
43 views

How can we show that if $f(n) = O(n^2)$, then $ f(n) = O(n^3)$

I'm looking at the 'positive constants' definition, but just not seeing how to go from here to there.
1
vote
1answer
29 views

Using Stirling's approximiation to show that $(\log(\log n))!$ is $O(n^k)$

I am trying to show the following: Prove, using Stirling's approximiation, that $(\log(\log n))!$ is $O(n^k)$ for some positive constant $k$. Stirling's approximation is $$n!=\sqrt{2\pi ...
2
votes
1answer
40 views

Asymptotic approximation for the r-associated Stirling numbers of the second kind

It is well know that for fixed $k$ the asymptotic approximation for the Stirling numbers of the second kind is given by $\frac{k^n}{k!}$. Does such simple asymptotic expression also exist for the ...
2
votes
0answers
32 views

Asymptotic analysis of certain multiple integration of power functions

Let $t_1,\ldots,t_m>0$, and $m\ge 4$ be an even integer. Consider the function: $$ f(a,b;\mathbf{t})=\int_0^{t_1}\ldots\int_0^{t_m} |x_1-x_m|^a |x_2-x_1|^b |x_3-x_2|^a |x_4-x_3|^b \ldots ...
0
votes
0answers
46 views

Biggest common sub-string search asymptotics

What is the function of Big-O in case where we use brute-force on two strings to find the biggest common sub-string. Please can you explain the underlying logic to the resulting formula corresponding ...
0
votes
0answers
28 views

Theoretical question of physical analogies to different O(f(x)) based characteristics of algoritms

I want to better understand the following concepts: "n!", "e^n". I.e. what is the physical analogy of the functions at the bottom of the message. F.ex. for the "n^a" and "log a x" where a equals to ...