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

learn more… | top users | synonyms (1)

8
votes
0answers
188 views

An integration to first order

I am having some trouble evaluating an integral -- involving taking an approximation. It would be great if someone could help me. I wish to evaluate $$\int_0^\pi {\cos\theta\cos \left[\omega ...
0
votes
1answer
107 views

Asymptotic dominance for sum of roots.

I'm trying to solve one of the tasks in the Algorithm Design Manual book from Steven Skiena. The goal is to place the functions into increasing asymptotic order. $f_1(n)=\sum_{i=1}^n\sqrt{i}$, ...
5
votes
1answer
357 views

Asymptotics for Bell number

Concrete Mathematics EXERCISE 9.46 Show that the Bell number $\varpi_n=e^{-1}\sum_{k\ge0}k^n/k!$ of exercise 7.15 is asymptotically equal to \[ m(n)^ne^{m(n)-n-1/2}/\sqrt{\ln n} \] where ...
4
votes
0answers
79 views

Dominated convergence on $e^{-n^2 t} t^{s/2-1}$

I am trying to apply the Dominated Convergence Theorem to show that $$\sum_{n\ge 1} \int_0^1 e^{-n^2 t} t^{s/2-1}dt= \int_0^1 \sum_{n\ge 1}e^{-n^2 t} t^{s/2-1}dt$$ as soon as $s>1$. I've ...
13
votes
6answers
896 views

A question on the Stirling approximation, and $\log(n!)$

In the analysis of an algorithm this statement has come up:$$\sum_{k = 1}^n\log(k) \in \Theta(n\log(n))$$ and I am having trouble justifying it. I wrote $$\sum_{k = 1}^n\log(k) = \log(n!), \ \ ...
1
vote
1answer
56 views

Big 0h question how are they similar?

How is an algorithm with complexity $O(n \log n)$ also in $O(n^2)$? I'm not sure exactly what its saying here, I feel it may be something to do with the fact that big-oh is saying less than or equal ...
7
votes
3answers
490 views

How to calculate $\sum \limits_{x=0}^{n} \frac{n!}{(n-x)!\,n^x}\left(1-\frac{x(x-1)}{n(n-1)}\right)$

What are the asymptotics of the following sum as $n$ goes to infinity? $$ S =\sum\limits_{x=0}^{n} \frac{n!}{(n-x)!\,n^x}\left(1-\frac{x(x-1)}{n(n-1)}\right) $$ The sum comes from Probability of ...
3
votes
1answer
128 views

Asymptotics of $\sum\limits_{j_1,\ldots, j_{2k}\neq n}\frac{1}{(n-j_1)(n-j_2)\cdots(n-j_{2k-1})(n-j_{2k})}$

How to estimate the following sum in terms of $n$? $$ \sum_{j_1,\ldots, j_{2k}\neq n}\frac{1}{(n-j_1)(n-j_2)\cdots(n-j_{2k-1})(n-j_{2k})}$$ with $n+j_1, j_1-j_2, \ldots, j_{2k}-j_{2k-1}, n-j_{2k} \in ...
9
votes
2answers
2k views

Compactly supported function whose Fourier transform decays exponentially?

It's well known now that a function can not be compactly supported both on the space side and the frequency side (so-called uncertainty principle). On the other hand a function can have exponential ...
5
votes
3answers
263 views

“$O$” notation in Stirling approximation

In the Stirling approximation the formula as typically used in applications is $$\ln n! = n\ln n - n +O(\ln(n))$$ I'm confused about the last term "$O$" . What does it mean actually, and when do we ...
4
votes
1answer
76 views

Asymptotic value in math.

What does the term $o(k^2)$ in $f(k)=k^2/2+o(k^2)$ mean ? I have used the asymptotic notation only in context of algorithmic complexity. With an analogy that, I am guessing it says $f(k)$ returns ...
8
votes
3answers
257 views

Asymptotic expansion of a series

I am interested in the asymptotics, as $x$ tends to $0$, of $$f(x) = \sum_{n=1}^\infty \frac{1}{n}\frac{1}{(e^{nx}-1)^2}$$ This function is well defined for every $x > 0$ (for example, use ...
3
votes
3answers
117 views

Result of Bernoulli trials being twice the expectancy?

Given a probability $0 < p < 0.5$ for success per trial with $n$ Bernoulli trials, what are the odds for having succeeded in at least $2np$ experiments?
2
votes
1answer
57 views

Series expansion and approximate solution

I have the following equation: $a(x)k-b(x)=0\Rightarrow k=\dfrac{b(x)}{a(x)}$. I find approximate solutions around $x=0$ by two ways: (1) I expand the equation as ...
1
vote
1answer
181 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 ...
0
votes
1answer
100 views

What is the vertical asymptote of $y=2x-\arccos(\frac{1}{x})$?

I have to find the vertical asymptote of $y=2x-\arccos(\frac{1}{x})$. So I have to find the limit of the function when $x$ approaches zero. In my textbook it says that the vertical asymptote does not ...
3
votes
0answers
184 views

Saddle point and stationary point approximation of the Airy equation

Happy New Year to you all. Let $$\tag 1 J(N)=\int_a^b e^{Nf(x)}dx$$ where $N\in\mathbb R$ and $N>>1$ and $f(x)$ has a global maximum at $x=x_0$ with Taylor expansion $$f(x) \approx ...
2
votes
3answers
82 views

How to find asymptotes of $y=ax+b+\frac{c+\sin x}{x}$

How can we find the asymptotes of $y=ax+b+\frac{c+\sin x}{x}$?
6
votes
2answers
2k views

Solving recurrence $T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + \Theta(n)$

I'm learning algorithms by myself and am using the excellent Introduction to algorithms to do that. It has been quite a long time since I last studied math, so maybe the solution to my problem is ...
2
votes
2answers
90 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 ...
4
votes
3answers
382 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 ...
2
votes
2answers
111 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? ...
4
votes
1answer
83 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 ...
7
votes
1answer
345 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
0answers
97 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 ...
3
votes
1answer
516 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 ...
2
votes
0answers
76 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)$ ...
3
votes
2answers
32 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
292 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 ...
0
votes
0answers
150 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 ...
1
vote
1answer
50 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 ...
8
votes
2answers
1k 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 ...
2
votes
1answer
248 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
96 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
101 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 ...
1
vote
0answers
41 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
66 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 ...
2
votes
1answer
143 views

Two asymptotics problems

Problem 1. Estimate $\displaystyle \sum_{i=1}^n \frac{\ln i}{\sqrt{i}}$ with an absolute error $O(1)$. Problem 2. Estimate: $$\left|\left\{ \langle a,b,c \rangle\in \mathbb{N}_+^3 : abc\le n ...
3
votes
1answer
65 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
223 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 ...
1
vote
2answers
919 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 ...
1
vote
1answer
129 views

Singularity analysis of integer power of logarithm ($\log^\beta (1-z)^{-1}$)

This is a theorem of Flajolet and Odlyzko (I think): Let $f(z)$ be a function analytic in a domain $$D = \{z : |z| \leq s_1, |\text{Arg}(z-s)| > \frac{\pi}{2} - \eta \},$$ where $s, s_1 > s,$ ...
2
votes
1answer
47 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 ...
0
votes
2answers
3k 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 ...
3
votes
1answer
2k 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 ...
2
votes
0answers
121 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 ...
3
votes
1answer
569 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} ...
0
votes
1answer
49 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
66 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 ...
8
votes
1answer
141 views

Comparing average values of an arithmetic function

Suppose $f(n)$ is a positive real-valued arithmetic function such that $$ \frac1n\sum_{k=1}^nf(k)\sim g(n) $$ for $g(x)$ a monotonic increasing function. What can be said about the asymptotic behavior ...