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

learn more… | top users | synonyms (1)

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 ...
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 ...
1
vote
1answer
127 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
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 ...
-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
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
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.
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 ...
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} ...
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
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 ...
8
votes
1answer
138 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 ...
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 ...
3
votes
2answers
127 views

The asymptotic behaviour for the probability that a random permutation in $S_n$ has order $2$.

Let $T_n$ be the number of elements of $S_n$ with order $1$ or $2$. It is well known that: $$ T_n = \sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\binom{n}{2k}(2k-1)!! = ...
0
votes
1answer
249 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.
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 ...
2
votes
4answers
599 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 ...
0
votes
3answers
3k views

Master Theorem for Solving $T(n) = T(\sqrt n) + \Theta(\lg\lg n)$

I'm trying to solve the recurrence relation: $$T(n) = T(\sqrt n) + \Theta(\lg \lg n)$$ My first step was to let $m = \lg n$, making the above: $$T(2^m) = T(2^{m\cdot 1/2}) + \Theta(\lg m)$$ If ...
3
votes
2answers
380 views

Solution of $T(n)=2T(n/2) + n\log(\log n)$

I am struggling to solve this equation: $$T(n)=2T(n/2) + n\log(\log n).$$ I concluded that the Master Theorem does not apply in this situation so I tried to successively substitute the terms in order ...
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) ...
6
votes
1answer
854 views

About the asymptotic formula of Bessel function

For $ \nu \in \Bbb R$, I want to prove the well-known formula $$ J_\nu (x) \sim \sqrt{\frac{2}{\pi x}} \cos \left( x - \frac{2 \nu +1}{4} \pi \right) + O \left( \frac{1}{x^{3/2}} \right) \;\;\;\;(x ...
0
votes
1answer
64 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 ...
28
votes
1answer
932 views

How does $ \sum_{p<x} p^{-s} $ grow asymptotically for $ \text{Re}(s) < 1 $?

Note the $ p < x $ in the sum stands for all primes less than $ x $. I know that for $ s=1 $, $$ \sum_{p<x} \frac{1}{p} \sim \ln \ln x , $$ and for $ \mathrm{Re}(s) > 1 $, the partial sums ...
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
2answers
86 views

Asymptotics of $nT(1) + \frac{n}{\lg5}\sum_{i=1}^{\log_5 n}\frac{1}{i}$

I am trying to find asymptotics/running time of recurrence $T(n) = 5T(\frac{n}{5}) + \frac{n}{\lg n}$. Since Master Theorem for solving the reassurances can't be used, I was able to unroll it and came ...
2
votes
0answers
211 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
200 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 ...
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 ...
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 ...
6
votes
2answers
136 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 ...
0
votes
1answer
121 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 ...
0
votes
2answers
183 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$ ...
3
votes
1answer
102 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
1answer
90 views

matrix “flag” clearing

I have a large matrix that is populated with a list of people, and a 1 or 0 as to whether or not they have a particular flag. A person can have one or more flags, or none at all. For example: $$ ...
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
1answer
253 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 ...