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

learn more… | top users | synonyms (1)

2
votes
0answers
55 views

A limit about $\prod_{k=0}^\infty\frac1{1-x^k}$

If $$\sum\limits_{n = 0}^\infty {{a_n}{x^n}} = \prod\limits_{k = 0}^\infty {\frac{1}{{1 - {x^k}}}} ,$$ Prove $${a_n} < \exp \left\{ {\sqrt {\frac{{2\pi }}{3}n} } \right\}$$ and $$\mathop {\lim ...
0
votes
1answer
34 views

Asymptotics of a real sequence in a Riemann sum

Let $t<0$ and $f(k)\in O(|k|^{t})$ a real function, $k\in\mathbb{Z}$. We consider $$a_n\cdot \sum_{k=1}^n \frac{1}{n} \frac{f(k)}{n^t}$$ where $a_n\subset \mathbb{R}$ and ...
0
votes
2answers
62 views

How to find the asymptotes of a square root function?

While working out some examples I'm trying to solve, I stumbled on a question that asks to find the asymptotes of the following function: $$y = \sqrt{x^2 + 3}$$ For rational functions I was thought ...
0
votes
0answers
14 views

Rate of growth of the negative part of even cumulants $(\kappa_{k})^{-}$ for mean zero, unit variance $X$

What is the rate of growth of $(\kappa_{2k})^-$ specifically in relation to $(2k)!$? The question was inspired by trying to find a lower bound for $$\kappa(t)+\kappa(-t)$$ by Taylor expanding ...
0
votes
1answer
42 views

Bounding a sum of logarithms

Consider a function $f:(0,\infty)\rightarrow \mathbb{N}$ with argument $\epsilon$. Suppose $f$ is decreasing in $\epsilon$. Let $0<b<1$, $K>0$, $d \in \mathbb{N}$, $\delta>0$. Assume $$ ...
19
votes
8answers
4k views

Stirling's formula: proof?

Suppose we want to show that $$ n! \sim \sqrt{2 \pi} n^{n+(1/2)}e^{-n}$$ Instead we could show that $$\lim_{n \to \infty} \frac{n!}{n^{n+(1/2)}e^{-n}} = C$$ where $C$ is a constant. Maybe $C = ...
0
votes
1answer
44 views

asymptotic analysis to solve differenial equation

$$ \frac{df(x)}{dx}+\bigg(1+\frac{1}{x}\bigg)f(x)=0 $$ how to solve above differential equation using asymptotic analysis ? Does that give an exact solution ?
1
vote
0answers
74 views

Asymptotic Expansion for a Function involving a Weird Integral

So I'm trying to find the asymptotic expansion as $x \to \infty$ of $$f(x)=\frac{1}{\bigg[A-\int \frac{\lambda^x}{\Gamma(x+1)}dx\bigg]^\frac{1}{\alpha}}$$ Note that $\lambda>0$ and $\alpha>0$. ...
1
vote
1answer
22 views

Use of asymptotically equivalent equations in limits

I was wondering about the steps to show that the following limit does not exists. $$\lim_{x\rightarrow\infty}[\log(x^2-3)-\log(x+2)]$$ I know that by using L'Hopital's Rule and the continuity of ...
0
votes
1answer
65 views

Series Expansion within a fraction

I'm currently reading "The cumulant lattice Boltzmann equation in three dimensions: Theory and validation" from Geier et. al. and have some trouble in a proof. We have given multivariat cumulants ...
0
votes
1answer
15 views

Complexity $\text{O}\left(\log(\log n))^{10}\right)$ vs $\text{O}\left((\log(\log n))^5\right)$?

If the question is not clear, then assume $t=\log(\log n)$, then the question can be re-framed as $\text{O}(t^{10})$ vs $O(t^5)$? So which has a higher order of growth? Thanks.
1
vote
0answers
24 views

Why can we act like functions are totally ordered by their orders?

For simplicity, consider only functions from $\Bbb N$ to $\Bbb R^{>0}$. Let $f\preceq g$ if there is an $A>0$ such that for all sufficiently large $n$, $f(n)\le A g(n)$. We normally would write ...
2
votes
2answers
35 views

Order of growth of the prime shift function

The prime shift function $s(n)$ for $n\in\Bbb N$ is defined by $$s\Big(\prod_ip_i^{e_i}\Big)=\prod_ip_{i+1}^{e_i},$$ where $p_i$ is the $i$-th prime. Here are the values of $s(1),\dots,s(100)$: ...
0
votes
0answers
24 views

Computation of $\sum_{i=0}^{m-1} n^{1/2^i}$

Basically, I'm just having issues computing this sum: $$ \sum_{i=0}^{m-1} n^{1/2^i} $$ where $m = \log_{2}({\log_{2}({n})})$. I need it in terms of $n$, as it's part of a runtime that I'm ...
2
votes
0answers
48 views

Nested trig asymptotics

Letting $\ \ \sin^n(x)=\underbrace{\sin\circ \sin\circ\dots\circ \sin(x)}_{n\text{ times}}\ $, is it true that $\ \ \sin^n(\pi/2)\sim \sqrt{\dfrac{3}{n}}?$ More specifically, is it true that ...
11
votes
3answers
305 views

Dealing with a difficult sum of binomial coefficients, $\sum_{l=0}^{n}\binom{n}{l}^{2}\sum_{j=0}^{2l-n}\binom{l}{j} $

I am interested in finding an upper bound for the sum $$F(n)= \sum_{l=0}^{n}\binom{n}{l}^{2}\;\sum_{j=0}^{2l-n}\binom{l}{j}$$ Ideally it should be possible to evaluate it exactly using some ...
0
votes
1answer
48 views

Mean value of a subharmonic function, divided by the logarithm of radius, has a limit

I am pretty stuck on a homework problem on harmonic functions, or rather subharmonic functions (which for us are allowed to take the value $-\infty$). The statement is as follows: Supper $u$ is ...
0
votes
0answers
17 views

Asymptotics of a series involving Incomplete Gamma function

The following is a series that involves Upper incomplete gamma function and I am trying to compute its asymptotics: $$ \frac{(n!)^2}{n^{2n+2}} \sum_{\substack{1 \leq i,j \leq n-1,\\\ 2\leq i+j \leq ...
0
votes
0answers
38 views

How small can we make two numbers $a$ and $b$, with prime factorizations such that…?

Given a number $n$, I'd like to find it using either the sum or difference of two other numbers. The other two numbers, which we can call $a$ and $b$, must have a prime factorization with no primes > ...
2
votes
1answer
82 views

How do you refute these conjectures that seem imply contradictory statements?

I've formulated two conjectures that seems to imply a strong result when are combined with well known equivalences of the Riemann hypothesis, and I would like to know how get a disproof of such ...
0
votes
3answers
48 views

Asymptotic Expansion, Regular Perturbation

Regular perturbation. Find the first two terms in an asymptotic expansion of the small parameter $ϵ$ of the solution of $$ xy'+y=ϵy^{1/2},\quad x>0,\quad y(1)=1. $$ Explain why the expansion ...
1
vote
1answer
29 views

Asymptotic expansion of roots of function

Find expansions for all roots of the equations below as epsilon → 0 with two nonzero terms in each expansion I don't see how drawing the graph will help. Also how do I go about balancing the sizes ...
11
votes
1answer
160 views

On the theorem “$3$ is everywhere”

In this Numberphile video it is stated that "almost all natural numbers have the digit $3$ in their decimal representation", and a proof of this fact is proposed. A sketch of the proof follows: ...
-1
votes
1answer
49 views

What will be the formula of $2^2 + 4^2 + \dots + n^2$? [duplicate]

I'm trying to understand how to calculate $2^2 + 4^2 + \dots + n^2$. I've only succeed to upper bound it by $\dfrac {n^3} 2$. My goal is to say that it is $\Theta (n^3)$. Thank you
2
votes
1answer
99 views

Use the limit rule to find Big Oh characterization of for loop

Find Big Oh characterization in terms of n, the professor says to use the limit rule for big Oh which says f(n) = O(g(n)) means f(n) "≤" g(n) => lim n->inf f(n)/g(n) = c where c is 0< c < inf ...
0
votes
1answer
17 views

Big O notation where C is negative

How do you prove the following? What I have so far:
2
votes
1answer
57 views

Question about asympotic expansion of $\int_0^x t\sqrt{ln(t)} dt$

Question: Find the constants $$a_0, a_1, a_2$$ in the asympotic expansion $$\int_0^x t\sqrt{ln(t)} dt$$ = $a_0(x^2)(lnx)^\frac 12$ + $a_1\frac {x^2}{(lnx)^\frac 12}$ + $a_2\frac {x^2}{(lnx)^\frac ...
0
votes
1answer
56 views

Finding a minimum spanning tree in a graph with edge weights in {1,2,.., R} where R is constant

I have recently been doing some research into algorithms for finding minimum spanning trees in graphs, and I am interested in the following problem: Let G be an undirected graph on n vertices with m ...
0
votes
1answer
26 views

Big Omega/Oh Notation (Application)

For clarity; I use the following definitions (taken from Wikipedia), in my question: Big Omicron: $f(n)=O(g(n))$. Formal definition: $\exists k >0,\exists n_{0}, \forall n>n_{0}: |f(n)| \leq k ...
0
votes
1answer
34 views

Why is $1+O(\frac{(\log n)^2}{n}) = 1-o(1)$?

I'm always surprised by the ease with which some authors use aymptotics. Here's the example that brought this up for me today: $1+O(\frac{(\log n)^2}{n}) = 1-o(1)$. I'm sure there's nothing too deep ...
-1
votes
1answer
46 views

The number of operations executed by algorithms A and B are $12n^3 + 40n \log n$ and $5n^4 -100n^2$ respectively.

The number of operations executed by algorithms A and B are $12n^3 + 40n \log n$ and $5n^4 -100n^2$ respectively. Determine an $n_0$ such that $B > A$ for $n \geq n_0$. so i got that $12n^3 + ...
1
vote
1answer
73 views

Upper bound for $\frac{\sum_{i=0}^{k} \binom{n-2}{i}}{\sum_{i=0}^{k} \binom{n}{i}}$

How to simplify $P = \frac{\sum_{i=0}^{k} \binom{n-2}{i}}{\sum_{i=0}^{k} \binom{n}{i}}$ to get an upper bound in terms of $n$ and $k$. Here $k \le n$ and $\binom{n}{r}$ is the binomial coefficient ...
0
votes
0answers
26 views

Richardson extrapolation for set of points

I have a boundary element method code which gives me the numerical solution of a problem. The finer mesh I use, the more exact will be the answer. So I have a set of points as my answers. I want to ...
2
votes
1answer
54 views

$f(x)\in O(\frac{1}{x})$ implies $\log(f(x))\in O(\frac{1}{x^2})$?

Consider a function $f(x):(0, \infty) \rightarrow \mathbb{R}$. Suppose $f(x)\in O(\frac{1}{x})$ as $x\rightarrow 0$ where Big O notation is described here. Is it true that $$ \log(f(x))\in ...
1
vote
1answer
28 views

How to prove/disprove Big $\Theta$

I would like to prove or disprove $$4^n = \Theta(2^n)$$ I think you may have to simplify the $4^n$ to $2^n*2^n$ but am unsure where to go from there. Any idea? Thank you
0
votes
1answer
28 views

What's the difference between “worst/best case big-O()” and omega()/theta()?

In formal discrete math and computer science we talk about "big-θ," "big-O," and "big-Ω" notation, being tight, upper, and lower bounds (respectively) on the growth of properties of an algorithm as ...
0
votes
0answers
14 views

What is the meaning of Big-Oh notation when obtaining bounds for loss functions?

I have seen the big-Oh notation used for loss functions before as a bound on $n$, which is usually taken to be the number of observed outcomes. However, my understanding of big-Oh notation is that it ...
5
votes
1answer
135 views

The function $\mathrm{Li}_2(x)=\int_2^x\frac{dt}{\log^2t}$, its inverse and summation

I am reading the more understandable mathematics in the section Preliminary Results of a paper in which the authors give a explanation of facts for the logarithmic integral and its inverse. In this ...
1
vote
1answer
53 views

Big-O Order and Best Big-O order for f(n)

I have some questions about Big-O notation: 1 Find the Big-O notation for the following sum: $1^2 + 2^2 + ... n^2$ 2 Find the best (i.e., lowest) Big-O order for $f(n)$, where $f(n) = 1 + 4 ...
6
votes
5answers
274 views

Arithmetic growth versus exponential decay

I have a kilogram of an element that has a long half-life - say, 1 year - and I put it in a container. Now every day after that I add another kilogram of the element to the container. Does the ...
2
votes
1answer
29 views

Poles with different behaviours

Is there a difference between the names of the poles at $x=0$ between: 1) $f(x)=\dfrac1x$ 2) $f(x)=\dfrac1{|x|}$ in that (1) tends to $+\infty$ as $x\to0^+$, and to $-\infty$ as $x\to0^-$, whereas ...
2
votes
0answers
26 views

Why is $n \exp (-\frac{2m}{n-2}) \ge e^{-w}$?

Here $m=\frac{1}{2}n(\log n + w(n))$. The full claim is that $$\left(1-o(1)\right) n \exp \bigg(-\frac{2m}{n-2}\bigg) \ge (1-o(1)) e^{-w}$$ but am I'm having trouble seeing why. Edit: ...
3
votes
0answers
18 views

A function related to divisior counting function

Let $d(n)$ be the divisor function. Let $d_{2}(n)=d(d(n))$, $d_{3}(n)=d(d(d(n)))$, $d_{4}(n)=d(d(d(d(n))))$ and so on... We're gonna define $f(n)$, the smallest number satisfies $d_{f(n)}(n)=2$. For ...
1
vote
0answers
36 views

asymptotic approximation for the sum of stirling numbers of the second kind

The Stirling number of the second kind, $S(n,k)$, is defined to be the number of ways one can partition an $n$-element set into exactly $k$ subsets. The sum over the values for $k$ from 1 to $n$ ...
3
votes
0answers
37 views

Asymptotic expansion of the harmonic numbers

I was skimming through Atle Selberg's "Elementary Proof of the Prime Number Theorem", and I got stumped at the part where he introduced equation 2.7 $(\sum_{v\leq z} \frac{1}{v} = log z + c_{1} + ...
8
votes
2answers
539 views

Approximation of $\mathrm{Li}(x) = \int\limits_{0}^x \frac{dt}{\ln t}$ [duplicate]

I am reading about the Riemann hypothesis, and the article mentioned the Li function: $$\mathrm{Li}(x) = \int\limits_{0}^x \frac{dt}{\ln t}$$ They said that this function can be approximated: ...
1
vote
1answer
86 views

Asymptotic expansion of $\sum_{n = 2}^{x} \frac{1}{\log(n)}$ and $\sum_{n=1}^{x}\frac{1}{\sum_{k=1}^{n}k^{-1}}$

Presumably \begin{align} \operatorname{Li}(x) = & \sum_{n = 2}^{x} \dfrac{1}{\log(n)}+ O(\log(x))\\ \end{align} where \begin{align} \operatorname{Li}(x) = & ...
3
votes
1answer
28 views

What is known about the asymptotics of Riccati's equation?

I'm interested in examining the asymptotic behavior of Riccati equations of the form $$ y'(x) = f(x) + g(x) y^2(x) $$ for $x \to \infty$. I've done some digging but I can't seem to find a simple ...
3
votes
0answers
70 views

When $\sum_{p*\leq n}\frac{1}{p*}\sim \log\log\log n$?

I have weird and vague question. We know the reciprocal of numbers $$\sum_{k\leq n}\frac{1}{k}\sim \log n$$ and reciprocal of primes $$\sum_{p\leq n}\frac{1}{p}\sim \log\log n$$ Now consider ...
0
votes
1answer
13 views

$\frac{n^{-h} - 1}{h} = -\log n + O(|h|(\log n)^2)$ for $|h|\log n \leq 1$

I'm trying to prove the continuity of $\zeta(s)$. As part of this proof, I've arrived at a term $$ \frac{n^{-h} - 1}{h} $$ which I want to bound. I wanted to see if it was possible to show that this ...