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

learn more… | top users | synonyms (1)

7
votes
1answer
276 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))$?
0
votes
2answers
626 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
229 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
446 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
211 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
249 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
58 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
243 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
691 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
188 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
97 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
43 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
235 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 ...
2
votes
4answers
556 views

Asymptotic behavior of $(1/2 + 2/3 + 3/4 + 4/5 + \cdots + (n-1)/n ) \times n$

I am interested in the following questions: given: $$G(n) = \left(\frac12 + \frac23 + \frac34 + \frac45 + \cdots + \frac{n-1}n\right)n$$ what is a $F(n)$ which could be an upper bound (clearly ...
3
votes
1answer
125 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 ...
0
votes
1answer
62 views

Question about oblique asymptotes

I'm looking for a way of finding an oblique asymptote of (on infinity): \begin{equation} \sqrt{1 + x^2 + \sqrt{(1 + x^2)^2 - 2 x^2 \cos^2{\theta}}} \end{equation} I know that the asymptote is ...
1
vote
0answers
31 views

What is the order of this expression?

Suppose I have $$C^2D^2 + C^4 - 2C^3D$$ where $C$ and $D$ are small numbers. The order should be worst case scenario, I am unsure how to write it. Can I say it's "order 2 in $C$" and "order 1 in $D$" ...
3
votes
1answer
43 views

Bounds on integral for computing expectation

I have a discrete random variable $X$ with $P(X \geq x) = c^x$ and I would like to bound $E(\log{X})$. I can write this as follows I think $$E(\log{X}) = \sum_{x=1}^{\infty} c^x \log{x}.$$ We know ...
0
votes
1answer
32 views

Naive question about asymptotics

Suppose I want to investigate the behaviour of say $\sin(\delta\ln(1+\epsilon))$ for variables $\delta$ and $\epsilon.$ I want to see what orders of $\delta$ and $\epsilon$ the term comes out as. I ...
0
votes
1answer
54 views

Is this line of thought for proving $\lim_{n \to \infty}S_n$ correct?

Say I have $S_n = \frac{n^n}{n!}$ nad I want to show that $\lim_{n \to \infty}S_n= \infty$. Is the following line of though correct, and if not, where any why am I wrong? Here $L(\cdot) = \log(\cdot)$ ...
2
votes
0answers
187 views

Asymptotic Methods - Boundary Layer Problems

I am currently studying a course in Asymptotic and Perturbation Methods and we have recently started discussing "Boundary Layer problems". It is not clear to me, however, exactly what form "Boundary ...
0
votes
1answer
243 views

Disproving asymptotic relation

I'm trying to disprove that $\forall f: N\rightarrow R^+,\forall g: N\rightarrow R^+, f \in \Omega(g) \iff \lfloor f\rfloor \in \Omega(\lfloor g\rfloor).$ However I need some hints.
1
vote
1answer
28 views

Simple Asymptotic Question

I was wondering if someone could help me figure out the asymptotic of $(1 + x)^{1/k}$, where $x$ is going to $0$ and $k$ is a fixed positive integer. I know it is going to 1, but I wanted to know the ...
1
vote
0answers
29 views

Polynomial time for a graph algorithm

Suppose an algorithm $A$ which, given a graph $G$ on $n$ vertices (represented in, say, adjacency matrix form) and some parameter $C$, runs in time $T = O\bigl(n^2\cdot \sqrt{C}\bigr)$. Is the ...
0
votes
1answer
197 views

Correct use of Big-O-notation

I'm a little bit unsure if I use the Big-O-notation in the following context correctly: Consider a function $\varphi \in C^{\infty}(\overline M)$ on a compact manifold with boundary and a boundary ...
5
votes
1answer
159 views

Almost all labeled graphs implies almost all graphs?

I would be thankful if someone could verify the following reasoning. Let $I$ be some graph property that is invariant (chromatic number, connectedness,etc.). Let $p(n)$ be the number of (labeled) ...
1
vote
1answer
41 views

Show something has a linear asymptote

Consider the function $z(x)=\sqrt{1+x^2}+1$ Show that $y=x+1$ and $y=1-x$ are linear asymptotes of the function at $\infty$ and respectively $- \infty$ So I started of with the first part: show that ...
3
votes
2answers
231 views

The geometric mean of primes less than or equal to $x$

I want to show that the limit of the geometric mean of primes less than or equal to $x$ is $e$ as $x \to \infty$. Is this correct? Using the product law of logarithms we have $$\ln \prod\limits_{p ...
0
votes
1answer
120 views

Prove that the little-o definition doesn't hold for two function (f and g)

I need your help with the following statement: Show there exist two function $f(n), g(n)$ such that meet the following definition: $g(n) = O(f(n))$ and $f(n) \ne O(g(n))$ But don't meet the ...
0
votes
2answers
139 views

Almost certainly incorrect proof about $\prod p$

Let p be prime. Assume (1): $\hspace{10mm} (\prod_{p\leq n} p)^{1/n} \sim e.$ Then $$(e^{\ln \prod p})^{\frac{1}{n}} = e^{(\sum \ln p)/n} \sim e \implies \lim_{n=1}^\infty \frac{e^{(\sum \ln ...
6
votes
2answers
134 views

Asymptotics of $\sum_{n=2}^\infty \frac{x^n}{(\log n) n!}$

I believe, based on numerical evidence, that $$\sum_{n=2}^\infty \frac{x^n}{(\log n) n!} \sim \frac{\exp(x)}{\log(x)}$$ as $x\to\infty$. However, I am not sure how to prove this. What would be a good ...
3
votes
1answer
97 views

Differential equation leading behavior

Show that the solution of $x^{3}y''=y$ whose leading behavior as $x\rightarrow0$ is $e^{-2x^{-1/2}}$ is actually given by $x^{3/4}e^{-2x^{-1/2}}$. Do this by writing $y=e^{S(x)}$ and finding the ...
3
votes
2answers
336 views

$L^p$ norm of multivariate standard normal random variable

Given $X_i\sim \mathcal{N}(0,1)$ what is the behaviour of $$ ||X||_{l^p}=(\sum_{i=1}^n|X_i|^p )^{1/p}$$ as $n\rightarrow \infty$? For $p=2$ results about $\chi$-distribution tell us that ...
0
votes
2answers
180 views

Some Big-O complexity definition proofs

I'm trying to prove (by definition) the following but to no avail: $n^{n/2} \ne O(3^{n/2}) $ $n! \ne O(3^n)$ $(n-b)^a = \Theta(n^a)$ $a,b $ are both constants whereas $a > 0 $ and $b$ ...
0
votes
2answers
1k views

Little-o proof by definition

I'm trying to figure out how to prove the following but to no avail. Given the following functions : $f(n) = n^3 -4n$ $g(n) = 5n^2 + 3n$ I have to show that $g(n) = o(f(n))$ by definition, that ...
7
votes
2answers
3k views

Value of Summation of $\log(n)$

Context: I am learning Dijstra's Algorithm to find shortest path to any node, given the start node. Here, we can use Fibonnacci Heap as Priority Queue. Following is few lines of algorithm: ...
1
vote
3answers
218 views

Order of magnitudes comparasions

I have a list of order of magnitudes I want to compare. My only idea is using calculus methods (limits , integral, etc...) to assert the functions relation. I need your help with the following. I ...
0
votes
3answers
81 views

Big-O compared to a new Operator

I'm trying to figure out a new operator compared to the Big O. Suppose we have two positive functions, $f(n)$ and $g(n)$ then we say that $f(n) = O^*(g(n))$ if there exists a constant $ c > 0 $ ...
2
votes
1answer
631 views

Orders of Growth between Polynomial and Exponential

What is known in contemporary mathematics about orders of growth for functions that exceed any degree polynomial, but fall short of exponential? This is a subject for which I've found little ...