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
3answers
563 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
493 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
273 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
477 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
155 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
424 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
417 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
425 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
217 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
169 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 ...
2
votes
0answers
196 views

Asymptotic bounds for a sum

I have this sum, which probably doesn't exist in closed form. $$\displaystyle ...
4
votes
3answers
1k views

Recurrence trouble: $T(n)=2T(n/2)+T(n/3)+\theta(n^2)$

I have to solve the following recurrence :$\displaystyle T(n)=2T(n/2)+T(n/3)+\theta(n^2)$ I have done the whole tree analyses and now I have to prove that $\displaystyle T(n) \leq ...
3
votes
2answers
587 views

Proving the bound on a recurrence relation

I am trying to prove the recurrence $2T(n-1) + 1$ has the bound $\theta(2^{n})$. $T(1) = \theta (1)$ My attempted solution: \begin{align*} T(n) &= 2T(n-1) + 1 \\ &= 2 \{ 2T(n-2) + 1 \} + 1 ...
1
vote
3answers
1k views

$T(1) = 1 , T(n) = 2T(n/2) + n^3$? Divide and conquer

$T(1) = 1 , T(n) = 2T(n/2) + n^3$? Divide and conquer, need help, I dont know how to solve it?
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
137 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
95 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( ...
3
votes
1answer
229 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
724 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 ...
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)$ ...
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) ...
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 ...
7
votes
1answer
251 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 ...
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} ...
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
158 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 ...
1
vote
3answers
343 views

Big Oh Question

I have the following question: Is the following statement true or false? ** All logs to base 2 log2n is a memeber of O(log(n)) My attempt: log2n - clogn <= 0 log2 + logn - clogn <= 0 1 + ...
6
votes
1answer
261 views

Algorithmic Analysis Simplified under Big O

Hi I am revising for my exams and I have the following inhomogeneous first order recurrence relation defined as follows: f(0) = 2 f(n) = 6f(n-1) - 5, n > 0 I ...
5
votes
2answers
177 views

An Alternate Proof to a Theorem Involving “e”

In a paper, it was claimed that $\lim_{x \to \infty} (1-\frac{f(x)}{x})^x \sim e^{-f(x)}$ when $\frac{(f(x))^2}{x}$ is $o(1)$. I proved the claim in the following way; however, I'm seeking a simpler ...
4
votes
2answers
145 views

Basic question about natural density

Suppose that we have a sequence of finite sets $A_1, A_2, \ldots$, which partition $\mathbb{N}$. I am making no other assumptions on the $A_n$ - i.e. there could be any amount of interleaving between ...
1
vote
1answer
184 views

Do equal mean and equal moment imply equal distribution?

If two sequences $\{a_k\}$ and $\{b_k\}$ are such that $$\lim_{n\to\infty}\frac{1}{n}\sum_{k=0}^{n-1}(a_k-b_k)=0$$ $$\lim_{n\to\infty}\frac{1}{n}\sum_{k=0}^{n-1}(a_k^2-b_k^2)=0$$ does it mean that ...
6
votes
1answer
155 views

Inequality on balls/bins with nested logs

Let $k = \lceil \frac{3 \ln n}{\ln \ln n}\rceil$. How does one show that $$ \left(\frac{e}{k}\right)^k \frac{1}{1-\frac{e}{k}} \le n^{-2} ? $$ This is from p. 44 of Motwani and Raghavan, Randomized ...
5
votes
2answers
361 views

Big $O$ vs Big $\Theta$

I am aware of the big theta notation $f = \Theta(g)$ if and only if there are positive constants $A, B$ and $x_0 > 0$ such that for all $x > x_0$ we have $$ A|g(x)| \leq |f(x)| \leq B |g(x)|. ...