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

learn more… | top users | synonyms (1)

1
vote
3answers
689 views

Show that $(n + a)^{b}$ = $\Theta(n^{b})$

In the book I'm following I got the following solution: To show that $(n + a)^b = \Theta(n^b)$, we want to find constants $c_1, c_2, n_0 > 0$ such that $$0 \leq c_1 n^b \leq (n + a)^b \leq c_2 ...
1
vote
1answer
4k views

How to prove that $\max(f(n), g(n)) = \Theta(f(n) + g(n))$?

Using the basic definition of theta notation prove that $\max(f(n), g(n)) = \Theta(f(n) + g(n))$ I came across two answer to this question on this website but the answers weren't clear to me. ...
2
votes
2answers
86 views

How to show $n! = \omega\big((\frac{n}{3})^{n+e}\big)$?

I'm learning some mathematics by myself and get stuck. The problem is to show that $n! = \omega\big((\frac{n}{3})^{n+e}\big)$, $\omega$ is the asymptotic notation. It's from the Problem Set 7 of MIT ...
2
votes
1answer
145 views

Does $\Theta(m \log n)$ and $0 < m < n^2$ imply $\Theta(n^2 \log n)$?

From a function in $\Theta(m + n^2)$ and $0 < m < n^2$, We conclude it is in $\Theta(n^2)$. Does a function in $\Theta(m\log n)$ so that $0 < m < n^2$, imply that it is in $\Theta(n^2\log ...
4
votes
3answers
291 views

Number of representable as sum of 2 squares

How to find asymptotically (or some reasonable bound, at least $ o(n) $) number of numbers, representable as a sum of squares of 2 numbers? (in case of bound I am interested in both: lower and upper ...
4
votes
1answer
78 views

Asymptotics with prime of form 4k+3

I wonder if there is some asymptotics for such sum: $ \sum_{p=2}^{n} \frac{1}{p}$, where the sum is taken over all primes of form $ 4k+3 $? It's well-known that $ \sum_{p=2}^{n} \frac{1}{p}$, where ...
2
votes
2answers
103 views

$f(x)=\int_{0}^{1}e^{ixz^2}dz$ as $x\rightarrow +\infty$.

Find the asymptotic behaviour as $f(x)=\int_{0}^{1}e^{ixz^2}dz$ as $x\rightarrow +\infty$. Could anyone show me how to do this with either the method of stationary phase or integration by parts? ...
1
vote
1answer
161 views

Matched Asymptotic Expansion - Stretching Transofrmation

I'm having problems getting my head around a stretching transformation in the method of matched asymptotic expansions. I'm reading Introduction to Perturbation Methods (by Holmes) and he discusses the ...
1
vote
0answers
90 views

Asymptotic analysis for multiple variables?

How is asymptotic analysis (big o, little o, big theta, big theta etc.) defined for functions with multiple variables? I know that the Wikipedia article has a section on it, but it uses a lot of ...
1
vote
0answers
81 views

“Balancing” two infinities

Given these two computational complexities of 2 algorithms: $\exp(O(\sqrt{\log n \log \log n}))$ $O(\sqrt{\exp n} / \log{ \sqrt{ \exp n} })$ where I imagine the first one goes to infinity slower ...
3
votes
2answers
30 views

Simple question about asymptotics of a ratio

What is the largest exponent $\alpha$ such that the ratio between $ n^{\alpha}$ and $ (\sqrt{n} / \log{ \sqrt n}) $ still remains asymptotically bounded (can assume $n$ positive integer) ?
0
votes
1answer
264 views

If $f(n) = \Theta (g(n))$, why does $g(n) = \Omega (f(n))$?

Why is this the case? I understand that if $f(n) = \Theta (g(n))$ then $c_1g(n)<f(n)<c_2g(n)$, but why does this show that $g(n)$ is bounded below by $f(n)$? I would think that it would be ...
2
votes
0answers
73 views

asymptotics of $ J_{iu} (ia)$ for a Bessel function

Let $J_{iu}(ia)$ be the Bessel function of imaginary order. ($a$ is a real number (positive or negative) and $u$ is also real.) In the limit $u \to \infty $ how does the function $J_{iu} (ia)$ ...
0
votes
0answers
115 views

prove that a big-o estimate is correct for a pair of functions

Please could someone review my proof of the following big-O estimate thanks $(n^2+8)(n+1)$ f(n) is O(g(n)) if there are positive constants C and k such that: (1)f(n) $\le Cg(n)$ whenever n>k ...
3
votes
1answer
318 views

Are there straightforward methods to tell which function has fastest asymptotic growth without a calculator?

For example, suppose I wanted to determine which of the following has the fastest asymptotic growth: $n^2\log(n)+(\log(n))^2$ $n^2+\log(2^n)+1$ $(n+1)^3+(n-1)^3$ $(n+\log(n))^22^{100}$ Are there ...
5
votes
2answers
255 views

Is there a function that only generates primes?

The title sums it up: does there exist a "nice" injective function $f(n)$ such that $f(n)\in\mathbb P$ for all $n\in\mathbb N$? I'm having difficulty specifying exactly what I want "nice" to mean, ...
1
vote
1answer
48 views

Asymptotics of a Product of Rational Expressions

The following is taken from page 8 of Alon and Spencer's The Probabilistic Method. $$ \prod_{i = 0}^{n-1} \frac{v - 2i}{v-i} \sim e^{-n^2/2v} $$ as long as $v \gg n^{3/2}$, estimating ...
2
votes
1answer
190 views

Rate of convergence of $\left[1+\frac{a}{x}\right]^x$ to $\operatorname{exp}[a]$ as $x\rightarrow\infty$

It's well-known that $\lim_{x\rightarrow\infty}\left[1+\frac{a}{x}\right]^x=\operatorname{exp}[a]$. I am wondering how fast does the limit converge as $x$ increases, and how the speed of convergence ...
0
votes
2answers
89 views

BIG-O proposed proof

I would like to prove that the statement $40^n = O(2^n) $ is false Would the following suffice as a proof? Let k be some arbitrary number. Let c = $\frac {40^k}{2^k}$. Then if n>k $\frac ...
1
vote
1answer
89 views

Asymptotic behaviour of $f(x) =f(\sqrt{x}) + \sqrt{x}$

I stumbled about this recursive function today: $$f_n = f_\sqrt{n} + \sqrt n$$ I tried to solve it with substitution ($m = \log_2 n, \quad g_{2^m} = g_{2^{m/2}} + 2^{m/2}$), but I have a bad feeling ...
7
votes
2answers
949 views

Big-O Interpretation

I have trouble understanding what the "Big O" notation, or asymptotic notation means. For instance, if you have $\sin(x)=x+O(x^3)$, what does this mean? Can anyone describe it in a simple way? I tried ...
1
vote
0answers
37 views

What is the big-$\mathcal{O}$ bound for the sum of function applied to the partitions of a set?

Consider a set $A$ that is partitioned into $n$ subsets $A_1 | A_2 | ... | A_n$ and a function $f \in \mathcal{O}(g)$. Question: what is the tightest bound I can establish for $\sum_{i=1}^n ...
0
votes
2answers
65 views

Asymptotic constants for a quadratic?

Note than $n$ is a parameter for the functions. For some constants $c_1, c_2$ and $n_0,$$$c_1n^2\le an^2 + bn + c \le c_2n^2$$ for all n > $n_0$. Consider any quadratic function $f(n) =an^2 ...
1
vote
1answer
91 views

Approximation of binomial distribution with normal distribution

The Central Limit Theorem implies that near the center of mass we can approximate the binomial distribution with the normal distribution: $$ P(B(n,p) \geq i) \approx P(Z \geq \frac{i - n p}{\sqrt{n p ...
3
votes
1answer
62 views

Exercise about MacLaurin's polynomial and small-o

In class the professor wrote the following limit: $\lim_{x\to 0} \frac{\sinh^2 (x) -x^2}{x^4}$ So he "expanded" (sorry for my English) the MacLaurin's formula for $\sinh x$ up to the 3rd power, and ...
3
votes
1answer
188 views

What are the asymptotics of the solution to $\log x=\epsilon x$?

I just read the question Why does $\ln(x) = \epsilon x$ have 2 solutions?, and thought I'd point out a related area of investigation. The equation $\log x=\epsilon x$ has 2 solutions for ...
7
votes
1answer
284 views

Is the derivative of a big-O class the same as the big-O class of the derivative?

Basically, for every function $f(x) \in O(g(x))$, is $f'(x) \in O(g'(x))$?
1
vote
2answers
661 views

Functions between polynomial and exponential

Does there exist a function $f(n)$ such that as $n \rightarrow \infty$, we have $p(n) < f(n) < e(n)$? Where $p$ is any polynomial and $e$ is any exponential (e.g. $e(n) = e^{\alpha n}, \alpha ...
3
votes
1answer
244 views

Asymptotics of exponential integral

Hello I wonder if there is any asymptotics known for such integral: $$ I(x) = \int_2^x \frac{e^t}{t} dt \qquad\text{when $ x\to+\infty $}. $$ Thank you very much.
1
vote
1answer
1k views

little-o and its properties

I know that $f(x) = o(g(x))$ for $x \to \infty $ if (and only if) $\lim_{x \to \infty}\frac{f(x)}{g(x)}=0$ Which means than $f(x)$ has a order of growth less than that of $g(x)$. 1) I'm still ...
3
votes
1answer
458 views

Comparing the asymptotic growth of two exponential functions

I'd like to compare the asymptotic growth rates of two functions: Cayley's formula for the number of trees on $n$ vertices: $n^{n-2}$ The number of possible graphs on $n$ vertices: $2^{n \choose 2} ...
2
votes
0answers
119 views

Are my calculations concerning the growth rate of $f(n) = \sum_{k=0}^n \min(2^k, 2^{2^{n-k}})$ correct?

Having $$f(n) = \sum_{k=0}^n g_n(k), \; g_n(x) = \min(2^x, 2^{2^{n-x}})$$ I want to know whether $\mathcal O(f(n)) \subsetneq \mathcal O(2^n)$. Since $g_n(x) \le 2^x$ it is at least $f(n) \in \mathcal ...
2
votes
1answer
217 views

Proof that limit goes to zero without Riemann-Lebesgue lemma

Let $\varphi$ be a test function ($\varphi$ is smooth and has compact support - is zero outside some bounded interval). I know that the following $$ \lim_{\epsilon \to 0_+} ...
0
votes
1answer
45 views

Find an example of function

Find an example of a function $f$ such that satisfies: $$\forall_{\varepsilon>0} \ f(n)=O(n^{1+\varepsilon})$$ but not $$f(n)=O(n)$$ I had been thinking about it for an hour and still can't find ...
2
votes
1answer
44 views

Asymptotics for sizes of cosets for non-normal subgroups

Let $G$ be a finite subgroup and $H$ a subgroup of index three in $G$, not necessarily normal. Put $n=|H|$. We choose representatives $a_1$ and $a_2$ such that $G$ is the disjoint union $$ G=H \cup ...
2
votes
2answers
255 views

limit of $\frac{(2n)!}{4^n(n!)^2}$

I'd love to understand the behaviour of the sequence $$ \frac{(2n)!}{4^n(n!)^2} \text{as } n \to \infty $$ the first step would be to simplify this to $$ \frac{(2n)(2n-1)(2n-2)\cdots(n+1)}{4^n \cdot ...
2
votes
1answer
61 views

Does $\omega(1)$ mean non-constant?

Let's say I have a discrete structure of size $n$, and some characteristic $a$ of that structure for which it holds that $a= \omega(1)$. Is this equivalent to say that $a$ can not be a constant but ...
-1
votes
2answers
2k views

What is the derivative of a summation with respect to it's upper limit?

For the moment, consider the corresponding problem involving integration. Let $s(x)$ be the explicit solution to the following integral. $ \displaystyle s(x)=\int_a^x f(t) \, dt $ The function ...
1
vote
1answer
149 views

Inequality for binomial coefficients

Let $m \leq n, n \leq N$ and $0\leq k \leq m$. I am wondering what is the dependence of $n$ and $N$ that for all $m, k$ $$ \frac{{N-m \choose n-k}}{{N \choose n}}\leq 1. $$ Thank you for your help.
0
votes
1answer
256 views

Formula for determining size at which one growth rate beats another?

My apologies if the title of the post is a bit confusing...wasn't sure how to word the problem. I ran across some questions in the form of: Suppose we are comparing implementations of insertion ...
2
votes
1answer
747 views

Method of dominant balance

Find the leading asymptotic behaviour as $x \rightarrow \infty$ of $$x^2y'' + (1 + 3x)y' + y = 0 $$ Can someone kindly explain me how to solve this problem? Im learning asymptotic analysis, and I ...
2
votes
0answers
51 views

Is this kind of approximation correct?

I was trying approximate the variance of a ratio of two random variables. I used to approximate it through Taylor's expansion: Assume $\sqrt{n}\big(X-E(X)\big)=O_p(1)$, ...
1
vote
1answer
208 views

Calculate asymptotes and local extreme values

I'm fed up with this question from my book. I've calculated the constants to this equation but got stuck at the asymptotes and local extreme values calculations which I need to plot the graph, perhaps ...
0
votes
1answer
63 views

Establishing an Inequality and Possible Circular Reasoning.

Let $0<\varepsilon \ll \delta$. Fix $\delta$. For any $k_0 \in \mathbb{N}$, I can deduce that $$1<\frac{\log n_k}{(1+\delta)^{k-k_0}\log n_{k_0}}<1+\frac{\log7}{\delta\log n_{k_0}}$$ ...
0
votes
2answers
53 views

Help with my flawed proof (A sequence of reals with 2 limits).

$(n_k)$ is a sequence of denominators for the sequence of prinicpal convergents of some irrational number, so $n_k \rightarrow \infty,\delta>0$. Let $0<\varepsilon \ll \delta$. I'm also given ...
0
votes
4answers
100 views

Big $\mathcal{O}$ notation problem

I need to show that the function $f(n) = n^2$ is not of $\mathcal{O}(n)$. If I am correct I should prove that there is no number $c,n \geq 0$ where $n^2\lt cn$. How to do that?
1
vote
1answer
44 views

Growth Rate of the Sequence of Denominators of the Sequence of Principal Convergents of an Irrational Number.

Let $\delta >0$. Take $\theta \in [0,1]-\mathbb{Q},$ let $\lbrace \frac{m_k}{n_k}\rbrace$ be the sequence of principal convergents to $\theta$, obtained from the continued fraction representation ...
2
votes
0answers
73 views

Bound the probability of unlikely escape through one end of a thin rectangle

Consider the following elliptic PDE boundary value problem, \begin{eqnarray} & a u_x + b u_y + \frac{\alpha}{2} u_{xx} + \beta u_{xy} + \frac{\gamma}{2} u_{yy} = 0 \;, \quad {\rm ~for~} ...
2
votes
2answers
50 views

Study of a series of functions

I've to study this series: $$\sum_{n=1}^\infty e^{\sqrt n\,x}$$ My teacher wrote that with the asymptotic comparison with this series: $$\sum_{n=1}^\infty\frac{1}{n^2}$$ My series converges ...
4
votes
1answer
249 views

How to show how primorials grow asymptotically?

The primorial $p_n\# $ is defined as the product of the first $n$ primes: $$p_n\# = \prod_{k = 1}^n p_k.$$ Asymptotically, primorials grow like $$p_n\# = e^{(1 + o(1))n\ln n)}.$$ How does one derive ...