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

learn more… | top users | synonyms (1)

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 ...
4
votes
1answer
662 views

Variations on the Stirling's formula for $\Gamma(z)$

I am currently reading some material that makes heavy usage of Hypergeometric functions, and there is one particular point about applying Stirling's approximation to various terms consisting of ...
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 + ...
0
votes
1answer
3k views

Prove that $\max(f(n),g(n)) = \Theta(f(n)+g(n))$ [duplicate]

Possible Duplicate: how can be prove that $\max(f(n),g(n)) = \theta(f(n)+g(n))$ How to prove $max(f(n),g(n)) = Θ(f(n)+g(n))$?
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: ...
1
vote
1answer
183 views

Question about $\Theta$ notation

Are statements below true or false? $(1+1/n)^n = \Theta(\log n)$ $\log \log n = o(\log n)$ Note that it is little-o, not big-O For first statement, I thought it would have $\Theta(n^2)$ complexity ...
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))}$$ ...
2
votes
1answer
209 views

Asymptotic order of $\frac{\mathrm{erfi}(\sqrt{x})}{\exp(x)\sqrt{x}}$

I need to approximate this expression in order to sum it. Asymptotically I obtain $\frac1{\sqrt{\pi}x}+\frac1{2\sqrt{\pi} x^2} + O\left(\frac1{x^3}\right)$. Although this looks fine there is the ...
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 ...
7
votes
2answers
372 views

Asymptotic behavior of the solutions to $\sin x = (\log x)^{-1}$

I apologize in advance for the length. The equation $\sin x = (\log x)^{-1}$ has exactly one solution $x_n$ in the interval $(2\pi n,2\pi n + \pi/2)$ for $n \geq 1$, and the exercise (de Bruijn, ...
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 ...
12
votes
3answers
823 views

Euler's Constant: The asymptotic behavior of $\left(\sum\limits_{j=1}^{N} \frac{1}{j}\right) - \log(N)$

I want to show that there exists a constant $C\in\mathbb{R}$ such that $$ \sum_{j=1}^N \frac1{j} = \log(N)+C+O(1/N). $$ I know how to prove that the Euler-Mascheroni constant exists (which I ...
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 $$ ...
7
votes
2answers
130 views

Why is $G(k)$ “more fundamental” than the Hilbert-Waring function $g(k)$?

In the Wikipedia entry for Waring's problem, the section on $G(k)$ starts as: “From the work of Hardy and Littlewood, more fundamental than $g(k)$ turned out to be $G(k)$, which is defined...” There ...
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
419 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 ...
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 ...
25
votes
1answer
852 views

How does $ \sum_{p<x} p^{-s} $ grow asymptotically for $ \text{Re}(s) < 1 $?

Note the $ p < x $ in the sum stands for all primes less than $ x $. I know that for $ s=1 $, $$ \sum_{p<x} \frac{1}{p} \sim \ln \ln x , $$ and for $ \mathrm{Re}(s) > 1 $, the partial sums ...
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 ...
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 ...
15
votes
3answers
1k views

How do you prove that $n^n$ is $O(n!^2)$?

It seems obvious that: $$n^n \in O(n!^2)$$ But I can't seem to find a good way to prove it.
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 ...
1
vote
2answers
83 views

what is the meaning of $a_n$ grows as for example $O(n\log n)$ or $O(n^2)$

Given a positive and increasing sequence $\{a_n\}$, what is the meaning of $a_n$ grows as for example $O(n\log n)$ or $O(n^2)$. I have read this in some books but the google search did not yield ...
0
votes
1answer
132 views

Does $f \sim g$ imply $f \asymp g$ in certain conditions?

I got a good answer to this question over on MathOverflow a while ago. Harald Hanche-Olsen claimed that, if $f, g: D\to \mathbb{R}^+$, then $$ f(x) \sim g(x) \implies f(x) \asymp g(x) \qquad \qquad ...
1
vote
1answer
110 views

Understanding a simplification in a theorem

I'm trying to understand a theorem in a paper on page 14/24. We are given that $$Z = (nq-1) \log \left(\frac{M+nq-1}{nq-1} \right) + M \log \left(\frac{M+nq-1}{M} \right) + \frac{1}{2} \log \left( ...
2
votes
0answers
197 views

Asymptotic bounds for a sum

I have this sum, which probably doesn't exist in closed form. $$\displaystyle ...
1
vote
1answer
60 views

Comparison of the order of two functions

This is along the lines of Problem 9.8. in 'Concrete Mathematics' by Graham, Knuth and Patashnik. Does any of the relation $\prec$, $\succ$ or $\sim$ exist between functions $f(n) =\displaystyle ...
1
vote
1answer
138 views

Does there exists a absolute measure for growth-rate of a function?

In computer science there are many notions of growth-rate of a function. These notions are, however, always relative in the sense that growth-rate of some function $f$ is always relative to some other ...
3
votes
1answer
96 views

Discovering Appropriate Bounds in Multivariable Asymptotics

I am having some difficulty with multivariable asymptotics. Let me provide a concrete example of the kind of thing I mean. Stirling's approximation for $n!$ is $$ n! \sim \sqrt{2 \pi n}\left( ...
1
vote
3answers
193 views

better understanding of incomplete gamma function $\Gamma(0,x)$

By definition incomplete Gamma function is:$$\Gamma(0,x)=\int_{x}^{\infty}t^{-1}e^{-t}dt $$ I have an expression which includes $$\Gamma(0,r(A)e^{i\phi(A)}),$$ where $A>0$ is a parameter, and ...
3
votes
1answer
230 views

Manipulating Equations with Big-oh

Note: first part is all context to question labeled "The Question" below: Working through the CLRS Introduction to Algorithms, 3rd ed, in Chapter 6.4 as they are talking about heaps they state: ...
3
votes
1answer
730 views

Determine if function is little-o, little-omega or big-theta

Let $f(n) = n^3(5+2\cos(2n))$ and $g(n) = 3n^2+4n^3+5n$. Given these two functions, I must determine the appropriate symbol where the underscore is: $f(n) \in \_(g(n))$ So, first thing to do is take ...
0
votes
1answer
91 views

Excercise: Ordering functions using the BigO notation

This was one of the previous year's exam questions. I have to order the following functions according to their growth rates using the $\mathcal O(n)$ notation. $f_1(n) = 2010 * \log_3(n^n)$ $f_2(n) ...
5
votes
1answer
109 views

For which x does $\sum\limits_{i=0}^{n}x^i=O(n)$ hold?

I'm stuck with this exercise: I have to find for which $x$ the estimate $\displaystyle\sum\limits_{i=0}^{n}x^i=O(n)$ holds. It seems intuitive to me that this must be the case for all $x \in (0,1)$ ...
4
votes
2answers
297 views

Is this the normal big-O?

My book on quantum mechanics introduces the notation $\mathcal O(1)$ as follows: We represent it by the formula $\Delta x \Delta k \gtrsim \mathcal O(1)$ where $\Delta x$ and $\Delta k$ are the ...
2
votes
2answers
653 views

Omitting bases in Logs -> Big O

Can anyone explain, with the aid of a mathematical proof, why bases are omitted in Big - O notation? EDIT: I don't understand how: NB: $\log_2(n) =$ log to the base 2 of n $log_2(n) = ...
1
vote
1answer
2k views

asymptotically larger vs polynomially larger

What is the difference between x being asymptotically larger than y and x being polynomially larger than y?
7
votes
1answer
91 views

Asymptotic Behavior of Iterated Sums

Given the integral identity \begin{align} \int_{0}^{t} \cdots \int_{0}^{t - t_{1} - \dots - t_{n -1}} 1 \ dt_1 \cdots dt_n = \frac{t^{n}}{n!}, \end{align} I believe it is true that \begin{align} ...
7
votes
1answer
252 views

Stochastic assignment problem

Given an $n \times n$ real matrix $C$, we can try to maximize $$\Phi(C, \pi) = \frac{1}{n} \sum_{i} C_{i,\pi(i)} $$ over $\pi \in S_n$, the set of all permutations on $n$ objects. What can one say ...
0
votes
1answer
338 views

Big O Rule Proof

Give a mathematical definition of the order notation $f(n) \in \mathcal O(g(n))$ and explain how this concept relates to the algorithmic idea of worst case analvsis. How do I go about answering ...
0
votes
2answers
160 views

Asymptotic probability: boys and girls in a line

We have $n$ people: $\alpha n$ are boys and $(1-\alpha)n$ are girls. They are standing in a line in a random order. We pick up one boy also at random. What can one say about the probability that ...