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
1answer
112 views

Is there any easier way to get the asymptotic value of this sum?

@Mike Spivey has proved in another question, that $$ S(n) = \sum_{k \geq 1} \frac{n!}{k (n-k)! n^k} = \sum_{k \geq 1} \frac{n^{\underline{k}}}{k n^k} \sim \frac{1}{2} \log(n). $$ But that proof is ...
4
votes
1answer
147 views

Does this sum go to 0?

If we define $$ S = \sum_{k=1}^{\lceil n/2 \rceil} \binom n k \left(\frac{k}{n}\right)^{2k} \left(1 - \frac{k}{n}\right)^{2(n-k)} $$ Then when $n\to \infty$, does $S \to 0$?
13
votes
4answers
435 views

Large $n$ asymptotic of $\int_0^\infty \left( 1 + x/n\right)^{n-1} \exp(-x) \, \mathrm{d} x$

While thinking of 71432, I encountered the following integral: $$ \mathcal{I}_n = \int_0^\infty \left( 1 + \frac{x}{n}\right)^{n-1} \mathrm{e}^{-x} \, \mathrm{d} x $$ Eric's answer to the linked ...
6
votes
2answers
119 views

What operations is this asymptotic relation closed under?

For all positive functions $f$ and $g$ of the real variable $x$, let $\sim$ be a relation defined by $f \sim g$ if and only if $\lim_{x \rightarrow \infty} \frac{f(x)}{g(x)} = 1$ Then if $f \sim g$, ...
0
votes
1answer
249 views

Finding a Big-O notation of: $\sum\limits_{i=1}^{k} ( t(a_i n)) + n$

I'm trying to find a Big-O notation of: $\displaystyle\sum_{i=1}^{k} ( t(a_in)) + n$, where $\displaystyle\sum_{i=1}^{k} (a_i) < 1$ using a recursion tree method and substitution method. I've ...
7
votes
1answer
524 views

the limit of the ratio of two $\Gamma(x)$ functions

I am interested in the quantity $$ a_{n} = \sqrt{n/2} \frac{\Gamma((n-1)/2)}{\Gamma(n/2)}$$ (this is the geometric bias of the non-central t-distribution with $n$ d.f.) After some plotting, my hunch ...
14
votes
2answers
345 views

What's the lower bound of the sum $S(n) = \sum_{k=1}^n \prod_{j=1}^k(1-\frac j n)$?

If we have $$ S(n) = \sum_{k=1}^n \prod_{j=1}^k(1-\frac j n) $$ What the lower bound of $S(n)$ when $n\to\infty$? PS: If I didn't make any mistake when I calculate $S(n)$, then it should be ...
5
votes
2answers
257 views

What's the asymptotic lower bound of the sum $\frac 3 2 + \sum_{k=3}^{n} \frac{n!}{k(n-k)!n^k}$?

The sum is: $$ S = 1 + 1/2 + \frac {(n-1)(n-2)} {3n^2} + \frac {(n-1)(n-2)(n-3)} {4n^3} + \ldots + \frac {(n-1)!} {n \times n^{n-1}}$$ $$= \frac 3 2 + \sum_{k=3}^{n} \frac{n!}{k(n-k)!n^k} $$ Can ...
2
votes
1answer
115 views

Asymptotics of an improper integral

I have to show that if $x \to \infty$, then $$ \int\limits_{\mathbb{R}^d} \frac{e^{i\xi x}}{\xi^2 + 2k\xi}d\xi = O\left(|x|^{-\frac{d-1}{2}} \right) \;\;\; \; d\geqslant2, \;\;\; k\in \mathbb{C}^d ...
27
votes
3answers
529 views

Sequence of numbers with prime factorization $pq^2$

I've been considering the sequence of natural numbers with prime factorization $pq^2$, $p\neq q$; it begins 12, 18, 20, 28, 44, 45, ... and is A054753 in OEIS. I have two questions: What is the ...
20
votes
2answers
746 views

Proof $\sum\limits_{k=1}^n \binom{n}{k}(-1)^k \log k = \log \log n + \gamma +\frac{\gamma}{\log n} +O\left(\frac1{\log^2 n}\right)$

More precisely, $$\sum_{k=1}^n \binom{n}{k}(-1)^k \log k = \log \log n + \gamma +\frac{\gamma}{\log n} -\frac{\pi^2 + 6 \gamma^2}{12 \log^2 n} +O\left(\frac1{\log ^3 n}\right).$$ This is Theorem 4 ...
8
votes
1answer
246 views

How do I prove $\sum_{n \leq x} \frac{\mu (n)}{n} \log^2{\frac{x}{n}}=2\log{x}+O(1)$? Can I use Abel summation?

I am wondering if it is possible to solve this problem using Abel summation: $$\sum_{n \leq x} \frac{\mu (n)}{n} \log^2{\frac{x}{n}}=2\log{x}+O(1)$$ Or maybe I am on the wrong track?
1
vote
1answer
108 views

Algorithm analysis, finding a constant c and a point n?

Say for example I say that: $$ 2n^2 + n - 8 \quad\text{is}\quad O(n^3) $$ To prove this I must find a constant $c$ and a point $n_0$ for which $n^3$ is an upper bound of the equation. This is ...
0
votes
1answer
563 views

Big O of polynomial functions

I am required to identify if $\log{(f(x))}$ is a subset of $O(\log{n})$ holds true for all polynomial functions. If I try with $f(x) = x^2$, then I am able to prove it to be correct. But, with $f(x) = ...
5
votes
0answers
191 views

Sums of Dirichlet-Characters over prime numbers (part 2)

This is kind of related to my previous question that was poorly stated because of misreading my own notes that I have taken on the papers I am currently reading, so no surprise that it eventually ...
2
votes
0answers
59 views

the nth power Logarithmic Integral [duplicate]

Possible Duplicate: Bounding the integral $\int_{2}^{x} \frac{\mathrm dt}{\log^{n}{t}}$ So I want to show that $$\int_2^x \frac{1}{\log^n(t)}\mathrm dt=O\left(\frac{x}{\log^n(x)}\right)$$, ...
3
votes
1answer
1k views

If f(n) = Θ(g(n)) does that also mean g(n) = Θ(f(n))?

I'm fairly certain that if f(n) = Θ(g(n)) is true, g(n) = Θ(f(n)) must also be true. However, I'm concerned I might be overlooking something. Am I correct in thinking that f(n) = Θ(g(n)) then g(n) ...
4
votes
1answer
131 views

How to estimate this integral

How to estimate the following integral: $$\int_e^x \log{\log{t}} dt$$ so that the error term is within $$O\left(\frac{x}{\log^2{x}}\right)$$. Assume $$x>e$$ Any hint?
2
votes
1answer
97 views

Proof $\frac{1}{(\frac{n}{3})!}=2^{-\Omega(n \log n)}$

I saw this in Wegener(2003), Methods for the Analysis of Evolutionary Algorithms as a upper bound on the probability. After applying Stirling approximation to $(\frac{n}{3})!$ I still keep getting ...
2
votes
2answers
244 views

Big O proof of statement

I am having a hard time proving that $n^k$ is $O(2^n)$ for all $k$. I tried taking $\log_2$ of both sides and have $k\cdot \log_2 n =n$ but this is wrong. I am not sure how else I can prove this. ...
1
vote
1answer
345 views

Finding the Big-O of $n^{\sin^2n} \cdot \sqrt{n}$

I need to find the Big-O of $f(n) = n^{\sin^2n} \cdot \sqrt{n}$. I know that the value of $\sin(n)$ oscillates between -1 and 1, and so does the value of $\sin^2(n) = \sin ( \sin(n))$. Now, if I am ...
3
votes
1answer
108 views

Can we do asymptotic calculation like this?

If we know $$ E(Z_i) = H_i + H_{n - i + 1} - 2 $$ and $i \sim \sqrt n$. Can we write: \begin{align*} E(Z_i) & = H_i + H_{n-i+1} - 2 \\ & \sim \log i + \log (n-i+1) \\ & ...
4
votes
1answer
278 views

Proving $n \log n \subseteq O(n^{1+\epsilon})$ without limits

How can one show that $n \log n \subseteq O(n^{1+\epsilon})$ where $0 < \epsilon < 1$ without using limits? This question arise from a homework where I used limits to prove the relation. I'd ...
23
votes
2answers
764 views

How to show that $\sum\limits_{k=1}^{n-1}\frac{k!k^{n-k}}{n!}$ is asymptotically $\sqrt{\frac{\pi n}{2}}$?

According to "Concrete Mathematics" on page 434, elementary asymptotic methods show that $\displaystyle \sum_{k=1}^{n-1}\frac{k! \; k^{n-k}}{n!}$ is asymptotically $\sqrt{\frac{\pi n}{2}}$. Does ...
10
votes
5answers
594 views

Bounding the integral $\int_{2}^{x} \frac{\mathrm dt}{\log^{n}{t}}$

If $x \geq 2$, then how do we prove that $$\int_{2}^{x} \frac{\mathrm dt}{\log^{n}{t}} = O\Bigl(\frac{x}{\log^{n}{x}}\Bigr)?$$
4
votes
2answers
338 views

Formally verifying that $n \log n = o(n^2)$

I am trying to verify that $n \log n = o(n^2)$ using the formal definition of small-o. The definition of small-o is as follows Let $f$ and $g$ be functions $f,g: \mathbb{N} \rightarrow \mathbb ...
4
votes
3answers
568 views

Proving that $2n^2+3n+1=O(n^2)$

For Big-O notation in mathematics, How does $f(n) = 2n^2 + 3n + 1 = O(n^2)$? Does it require any more information for the proof? Edit: ...
18
votes
2answers
498 views

Asymptotic behaviour of sums of consecutive powers

Let $S_k(n)$, for $k = 0, 1, 2, \ldots$, be defined as follows $$S_k(n) = \sum_{i=1}^n \ i^k$$ For fixed (small) $k$, you can determine a nice formula in terms of $n$ for this, which you can then ...
6
votes
2answers
102 views

Is this asymptotic equation correct?

Is this equation correct? $$ \frac {1 + \Theta(\frac 1 {2n})} {(1 + \Theta(1/n))^2} = 1 + O(1 / n) $$ I need this equation to prove that $$ \binom {2n} n = \frac {2 ^ {2n}} {\sqrt {\pi n}} (1 + ...
4
votes
1answer
158 views

Asymptotic Approximation for a Derangement Algorithm

Asymptotic Approximation for a Derangement Algorithm I have been analyzing the complexity of a simple algorithm for randomly generating a derangement, i.e., a permutation $\pi$ with no fixed points: ...
0
votes
3answers
185 views

Using $O(n)$ to determine limits of form $1^{\infty},\frac{0}{0},0\times\infty,{\infty}^0,0^0$?

Is it sufficient to use $O(n)$ repeatedly on $1^{\infty},\frac{0}{0},0\times\infty,{\infty}^0,0^0$ to get determinate forms? For example if we look at $\frac{0}{0}$ then $$\frac{O(f(n))}{O(g(n))}$$ ...
1
vote
2answers
2k views

Asymptotic expansion of tanh at infinity?

Does $\tanh(x)$ have an asymptotic expansion for $x \rightarrow \infty$?
1
vote
0answers
89 views

Asymptotic behaviour of the solution to a certain PDE

$\delta M=\beta(x-y)M_y+\mu x(y-1)M_x+\delta y$, where $M(x,y)=\sum_{n=0}^{\infty}{\sum_{k=0}^{\infty}{s_{n,k}x^ny^k}}$ is the generating function for a certain probability distribution $\{s_{n,k}\}$ ...
2
votes
1answer
276 views

Asymptotic error of Fourier series partial sum of sawtooth function

In Iwaniec's book, Topics in Classical Automorphic Forms, pg. 4, he gives the statement: $$\{x\}=\frac{1}{2}-\sum_{n=1}^N\frac{\sin 2\pi nx}{\pi n}+O((1+||x||N)^{-1})$$ where $\{x\}$ denotes the ...
2
votes
2answers
479 views

On the growth order of an entire function $\sum \frac{z^n}{(n!)^a}$

Here $a$ is a real positive number. The result is that $f(z)=\sum_{n=1}^{+\infty} \frac{z^n}{(n!)^a}$ has a growth order $1/a$ (i.e. $\exists A,B\in \mathbb{R}$ such that $|f(z)|\leq ...
2
votes
2answers
336 views

Solving recurrences of the form $T(n) = aT(n/a) + \Theta(n \log_2 a)$

The time complexity for the merge sort algorithm is $T(n) = 2T(n/2)+\Theta(n)$, and the solution to this recurrence is $\Theta(n\lg n)$. However; assume you are not dividing the array in half for ...
3
votes
1answer
92 views

Asymptotics where the absolute error goes to 0 - what are these called?

Say I have a function $f$ for which $\lim_{x\rightarrow\infty}f(x)=\infty$ and which I'd like to approximate by a simpler function $g$. We say $g$ is an asymptotic for $f$ iff $$ ...
3
votes
4answers
156 views

Equality of outcomes in two Poisson events

I have a Poisson process with a fixed (large) $\lambda$. If I run the process twice, what is the probability that the two runs have the same outcome? That is, how can I approximate ...
7
votes
3answers
426 views

Why is $\sum_{k = n}^{\infty} (\log k)^2/k^2 = O \left((\log n)^2/n \right)$?

The question comes from a statement in Concrete Mathematics by Graham, Knuth, and Patashnik on page 465. $$\sum_{k \geq n} \frac{(\log k)^2}{k^2} = O \left(\frac{(\log n)^2}{n} \right).$$ How is ...
10
votes
1answer
418 views

Asymptotic estimate for Riemann-Lebesgue Lemma

Let $f$ be a real-valued, $L^1$ integrable function on the interval $[a,b]$. Then the Riemann-Lebesgue Lemma tells us that: $$\int_a^bf(x)\sin(2\pi nx)dx\rightarrow0 \text{ as } ...
0
votes
2answers
437 views

Estimate the average number of prime factors of a 1000-digit number

More formally, find an asymptotic for $N\to\infty$ of $$\frac{\sum_{1\le k\le N} M(k)}{N}$$ where $$M(p_1^{d_1}p_2^{d_2}\cdots p_k^{d_k}) = d_1+d_2+\cdots+d_k$$ For example, $M(24) = M(2^3\cdot3) = ...
0
votes
2answers
115 views

Calculating Running Time 101

I need to learn how to prove/disprove each of the following. Anyone able to do it in very simple way for a NON -mathematician to easily understand? ( NB -- NOT HOMEWORK) a) $$n^2 + n + 1 = \Theta ...
1
vote
1answer
121 views

$T_{3}=\Theta(n^{0.99}) ,T_{2}=\Theta(n^{\log\log n}),T_{1}=\Theta\left(\frac{n}{\log n}\right)$

$T_{3}=\Theta(n^{0.99}),\quad T_{2}=\Theta(n^{\log\log n}),\quad T_{1}=\Theta \left(\frac{n}{\log n}\right)$ I need to decide what is the relation (ratio?) between $ T_{1},\, T_{2},\, T_{3}$? So by ...
10
votes
2answers
317 views

Positive integers $k = p_{1}^{r_{1}} \cdots p_{n}^{r_{n}} > 1$ satisfying $\sum_{i = 1}^{n} p_{i}^{-r_{i}} < 1$

A divisor $d$ of $k = p_{1}^{r_{1}} \cdots p_{n}^{r_{n}}$ is unitary if and only if $d = p_{1}^{\varepsilon_{1}} \cdots p_{n}^{\varepsilon_{n}}$, where each exponent $\varepsilon_{i}$ is either $0$ or ...
4
votes
1answer
1k views

Hardy Ramanujan Asymptotic Formula for the Partition Number

I am needing to use the asymptotic formula for the partition number, $p(n)$ (see here for details about partitions). The asymptotic formula always seems to be written as, $ p(n) \sim ...
2
votes
3answers
273 views

Recursion equations: $T(n)=T(\frac{n}{4})+T(\frac{3}{4}n)+1$

What's the simplest way to prove that the solution for this recursion equation: $T(n)=T(\frac{n}{4})+T(\frac{3}{4}n)+1$ , is $T(n)=\theta (n)$? I think that it is $T(n)=\theta (n)$ because it is ...
2
votes
1answer
112 views

Obtaining an asymptotic lower bound on a function

A follow-up question to this one basically Understanding a simplification in a theorem. If you want to see the original paper, see page 6/24 there. We are given that $2 < n \leq M \leq n^2$. Then, ...
2
votes
2answers
218 views

How to show that a “Big-Oh” set is a subset of another?

Let's say we have two "Big-Oh" sets called $\text{Constant}$ and $\text{Logarithmic}$, such that one has $O(1)$, and the other has $O\big(\log(n)\big)$, respectively, how would I show that ...
2
votes
2answers
128 views

Show that $f \in \Theta(g)$, where $f(n) = n$ and $g(n) = n + 1/n$

I am a total beginner with the big theta notation. I need find a way to show that $f \in \Theta(g)$, where $f(n) = n$, $g(n) = n + 1/n$, and that $f, g : Z^+ \rightarrow R$. What confuses me with this ...
5
votes
1answer
171 views

Asymptotic formula for $k$-partitions of a number

Asymptotic formula for all the partitions of a number is given by $$p(n) \sim \frac{1}{4n\sqrt{3}} e^{\pi \sqrt{\frac{2n}{3}}}$$ Only fraction of those will be $k$-partitions. What is asymptotic ...