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

learn more… | top users | synonyms (1)

-1
votes
2answers
399 views

Two questions in asymptotic notation

I have to prove two equations and I can't understand them. Any help would be grateful because I have to consign the whole project in two days. These are the equations: If $f(n)=O(g(n))$ and ...
7
votes
1answer
240 views

Bounds on $\sum_{k=0}^{m} \binom{n}{k}x^k$ and $\sum_{k=0}^{m} \binom{n}{k}x^k(1-x)^{n-k}, m<n$

I've read this interesting article by Woersch (1994) dealing with approximation of binomial coefficients (rows of Pascal's triangle). I'm just wondering if similar bounds exist for partial binomial ...
2
votes
1answer
286 views

Prove that $e^{\sqrt{\log x }}=O(x^n)$

I have to prove the following: Let $n \in \mathbb{N}$. Proove: $$e^{\sqrt{\log x}}=O(x^n) .$$ I just know the definition of $O$: $f(x), g(x)$ are real functions. $f(x)=O(g(x))$ means, that for ...
2
votes
1answer
244 views

If $f(n) \in O(g(n))$, then $f(n)+g(n) \in \Theta (g(n))$

I am a total beginner with the big O and big theta notation. How would I prove the following? If $f(n) \in O(g(n))$, then $f(n)+g(n) \in \Theta (g(n))$. I am not sure how to go from the ...
1
vote
0answers
119 views

Question concerning application of l'Hôpital's rule

Prove: If g is strictly positive then $\int_{2}^{x}o(g)\,dt = o\left(\int_{2}^{x}g\,dt\right)$. I understand this question to mean: prove that $f=o(g)$ implies $F = o(G)$ and conversely. Please ...
3
votes
2answers
92 views

Is $O(\frac{1}{n}) = o(1)$?

Sorry about yet another big-Oh notation question, I just found it very confusing. If $T(n)=\frac{5}{n}$, is it true that $T(n)=O(\frac{1}{n})$ and $T(n) = o(1)$? I think so because (if ...
7
votes
1answer
241 views

Mixing two different biased coins

My problem is as follows: I have two biased coins with probabilities $p_1$ and $p_2$ of landing heads. I start with coin 1 and toss it until it lands heads. Then I swap to coin 2 and toss until it ...
2
votes
2answers
63 views

Can I simplify $\log_3{n} \cdot 2^{\log_3{n}} \cdot n$

Is it possible to simplify $$\log_3{n} \cdot 2^{\log_3{n}} \cdot n$$ I am actually trying to find the Big-O notation for this equation. But if you don't know what it is, is it possible to simplify ...
0
votes
1answer
133 views

Big-O notation question

We say that $f(x) = O(g(x))$ if there exists a constant $C$ such that $|f(x)| \leq C|g(x)|$ for all $x \in \mathbb{R}$ (or whatever we take our domain to be). What is meant explicitly by the statement ...
0
votes
1answer
193 views

How one can prove $o(g(n)) \cap \omega (g(n))$ is empty?

From definition of $o$ and $\omega$ one states that $0 < c_1\cdot g(n) < f(n)$ for $n > n_0$ and some $c_1$ and another states that $0 < f(n) < c_2\cdot g(n)$ for $n > n_1$ and some ...
2
votes
1answer
158 views

Asymptotic expansion of an integral

Here is an exercise from Dieudonné. He suggests to "perform integrations by part". Let $f, g$ be positive $C^\infty$ functions, $F(x)=\int_1^x f(t)dt$ and assume that $\int_1^\infty f(t) dt = ...
2
votes
2answers
2k views

Efficient algorithm to find maximum of a unimodal sequence

We have $a_{1}<a_{2}<\dots <a_{p}$ and $a_p > a_{p+1}>\dots>a_{n}$. We want to find the maximum element $a_{p}$ of a unimodal sequence reading as few elements is possible. I want to ...
13
votes
4answers
343 views

Asymptotic formula for $\sum_{n \le x} \frac{\varphi(n)}{n^2}$

Here is yet another problem I can't seem to do by myself... I am supposed to prove that $$\sum_{n \le x} \frac{\varphi(n)}{n^2}=\frac{\log x}{\zeta(2)}+\frac{\gamma}{\zeta(2)}-A+O \left(\frac{\log ...
0
votes
2answers
111 views

Finding $\Omega(f(n))$

Is there a standard way to find a $\Omega$ of a function $f(n)$ ? I mean, I'm trying to understand how to determine: $$g(n)=\Omega(f(n))$$ where $f(n)$ is a polynomial or logarithmic function I ...
4
votes
1answer
126 views

Least cardinality of a set of integers

If $S_n$ is a set of positive integers >0 of the least cardinality such that every positive integer less then $n$ can be written as the sum of at most two elements of $S_n$, how precisely can we bound ...
2
votes
1answer
157 views

Asymptotic formula of $\sum_{n \le x} \frac{d(n)}{n^a}$

As the title says, I'm trying to prove $$\sum_{n \le x} \frac{d(n)}{n^a}= \frac{x^{1-a} \log x}{1-a} + \zeta(a)^2+O(x^{1-a}),$$ for $x \ge 2$ and $a>0,a \ne 1$, where $d(n)$ is the number of ...
3
votes
2answers
2k views

Central Limit Theorem and sum of squared random variables

This is a two-part question. Suppose I am drawing random variables $X_i\sim A$, $1\leq i \leq n$ where $A$ is a zero-mean, finite variance $\sigma_A^2$, symmetric probability distribution having ...
5
votes
3answers
584 views

Asymptotics of terms and errors in Stirling's Approximation

I have two related questions. Both are related to the asymptotics of Stirling's approximation, which is why I have included them in the same question. I will separate the questions if it is deemed ...
20
votes
5answers
681 views

Asymptotics of $1^n + 2^{n-1} + 3^{n-2} +\cdots + (n-1)^2 + n^1$

Suppose $n\in\mathbb{Z}$ and $n > 0$. Let $$H_n = 1^n + 2^{n-1} + 3^{n-2} +\cdots + (n-1)^2 + n^1.$$ I would like to find a Big O bound for $H_n$. A Big $\Theta$ result would be even better.
0
votes
1answer
58 views

Finding the asymptotics of a summation

Let $n\in\mathbb{Z}^+$ and $T_n = 1\sqrt{1} + 2\sqrt{2} +\cdots+ n\sqrt{n}$. Finding $\mathcal{O}(T_n)$, $\mathcal{\Omega}(T_n)$ and $\mathcal{\Theta}(T_n)$
8
votes
2answers
465 views

Equivalence to the prime number theorem

I was just reading this question and answer: How will this equation imply PNT and it raised a whole new question: Given that $\sum_{n\le x} \Lambda(n)=x+o(x)$, prove that $$\sum_{n\le x} ...
0
votes
1answer
275 views

If $f(n) = \Theta(g(n))$, then $cf(n) = \Theta(g(n))$ for any $c \neq 0$

How would I prove: If $f(n) = \Theta(g(n))$, then $cf(n) = \Theta (g(n))$ for any $c \neq 0$. I'm pretty sure it's true, but not sure how to prove it.
0
votes
1answer
38 views

Approximation of $ n^a \int_{0}^{\pi/n}\sin^b(t)dt $

How can I find an approximation of $$ n^a \int_{0}^{\pi/n}\sin^b(t)dt $$ when $ n\rightarrow \infty$, $(a,b>0)$ ?
0
votes
2answers
74 views

Summation identity involving logarithm

I'm having trouble understanding why this identity holds: $$\sum_{k=0}^{(\log n) - 1} \frac{n}{\log (n - k)} + \theta(1) = \sum_{k=1}^{\log n} \frac{n}{k}+ \theta(1) $$ Any pointers to a proof ...
4
votes
0answers
87 views

Asymptotic Analysis of Complex Integrals

Let $\gamma\subset B(0,2)\subset \mathbb{C}$ a smooth Jordan curve envolving the origin and $\phi:\mathbb{C}\setminus (-\infty,0)\to \mathbb{C}$ an analytic function having finite boundary values, ...
0
votes
2answers
1k views

How do I prove $f (n) = \omega(2^n)$ if $f(n) = n!$? [closed]

How do I prove $2^n = \Omega(n^2)$?
1
vote
1answer
651 views

Little 'o' / Big 'O' Definitions

I understand, or at least think I understand, the nature of a function that is "little o": If $f$ is a function between Banach spaces E and F, then it is "little-o" if $$|x|\rightarrow 0 \implies ...
7
votes
2answers
313 views

Asymptotics of $\sum_{k=0}^{n} {\binom n k}^a$

I need to estimate the asymptotics of $$\sum_{k=0}^{n} {\binom n k}^a, \quad a>2, \quad a \in \mathbb{N}$$ In particular, I'm pretty much interested in $a=4$ case, but if the general solution ...
4
votes
3answers
903 views

How to show $\sum_{i=1}^n\log(n/i)= \Theta(n)$?

Is the sum from i=1 to n for log(n/i) = Θ(n)? Im studying for a test and appreciate your help. This is what I did: and got something else $$\sum_{i=1}^n \log(n/i)=\sum_{i=1}^n[\log n-\log ...
3
votes
1answer
64 views

Number counting functions related to simple groups and asymptotic law of distribution

We say that an positive integer $n$ is a simple number if there exist a non abelian simple group of order $n$. Denote by $\mathfrak{s}$ this set. prime-power number if it is of the form $n=p^a$, ...
5
votes
1answer
69 views

Asymptotics of $\sum_{i=1}^{n^2 - 1} \frac{i^2}{[\frac{n^3}{3}]^2}$

I need to somehow figure out what happens with the following sum: $$\sum_{i=1}^{n^2 - 1} \frac{i^2}{[\frac{n^3}{3}]^2}$$ when $n \rightarrow \infty$. Should it be zero? Should it be a constant? ...
1
vote
3answers
350 views

big and small O notation help

I was hoping someone could help me answer this question. I can't wrap my head around this concept: Why is $\cal{O}(x^3) = o(x^2)$?
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 ...
0
votes
1answer
240 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
450 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 ...
6
votes
2answers
114 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$, ...
8
votes
1answer
212 views

Analytic number theory primer — sequences and series

For a book like Titchmarsh, or Iwaniec and Kowalski, it seems a thorough knowledge of asymptotics is a prerequisite. What are good books for training oneself in such manipulation of asymptotics, ...
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
421 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 ...
13
votes
2answers
338 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
254 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
113 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 ...
10
votes
2answers
402 views

Asymptotics of LCM

Let $\operatorname{LCM}(x_1,x_2,\ldots,x_n)$ be the least common multiple of the integers $x_i$. How can one find the asymptotics of $\operatorname{LCM}(f(1),f(2),\dots,f(n))$ as $n$ approaches ...
5
votes
1answer
132 views

An estimate of a series

Suppose $s$ is not an integer, let $\lambda(s)=\min_{n≥0}|s+n|$. Show that $\sum\limits_{n=1}^{\infty}(\frac{1}{n+s}-\frac{1}{n})\ll\frac{1}{\lambda(s)}+\log(|s|+2)$.
2
votes
2answers
95 views

What is the asymptotic bound for this recursively defined sequence?

$f(0) = 3$ $f(1) = 3$ $f(n) = f(\lfloor n/2\rfloor)+f(\lfloor n/4\rfloor)+cn$ Intuitively it feels like O(n), meaning somewhat linear with steeper slope than c, but I have forgot enough math to not ...
1
vote
1answer
100 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
502 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) = ...
1
vote
2answers
326 views

Is this time complexity example correct?

This is probably not the best worded question but here goes. I've been reading a text book trying to get my head around time complexity. I understand the most of it, but this example has threw me. ...
5
votes
0answers
178 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)$$, ...