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

learn more… | top users | synonyms (1)

0
votes
1answer
43 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
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 ...
1
vote
0answers
73 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$. ...
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
34 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
47 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 ...
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 > ...
0
votes
1answer
64 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
41 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 $$ ...
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
46 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 ...
10
votes
1answer
158 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
0
votes
1answer
17 views

Big O notation where C is negative

How do you prove the following? What I have so far:
4
votes
3answers
69 views

Extracting the divergent part of an integral

I want to evaluate the integral $$ \int_0^1 \frac{2x(x-2)(1-x)}{(1-x)^2 + ax} \, \mathrm{d}x$$ in the limit of small $a$. For $a = 0$ this integral is divergent due to the $1/(1-x)$ pole. The exact ...
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
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
1answer
38 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 ...
1
vote
1answer
70 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
53 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
27 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
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 ...
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 ...
0
votes
1answer
27 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 ...
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: ...
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 ...
6
votes
5answers
270 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 ...
3
votes
0answers
17 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 ...
3
votes
0answers
36 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} + ...
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 ...
1
vote
1answer
29 views

Bounded in probability order

Given that $X_1,\ldots,X_n$ are $n$ independent and identically distributed random variables. We know that they have finite moments up to third order e.g. $EX_i=0$, $EX_i^2<\infty$ and ...
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 ...
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 ...
0
votes
0answers
48 views

Big O, Omega and Theta Notation Properties

As an exercise, we have to prove or disprove certain statements about the properties of Big O Notation. I struggle with two of those right now. "For all $a,b \in N, a \le b: n^{\frac{1}{a}} \in ...
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$ ...
2
votes
2answers
48 views

What is the asymptotic behaviour of $\sum_{p_k\leq x}kp_k$, where $p_k$ is the kth prime number?

I would like to study the asymptotic behaviour of this sequence A014285, see as OEIS, that seems has few references and a good behaviour (see the sequence as graph) $$\sum_{k=1}^nkp_k,$$ where $p_k$ ...
4
votes
1answer
145 views

Functions that preserve asymptotic equivalence

Is there any notion of preserving asymptotic equivalence by a real-valued function? Any facts known about such functions? To clarify what I'm asking I'll introduce one formalization of the idea which ...
0
votes
2answers
51 views

Function with an asymptote at y=-1 and y=1

I'm looking for a function that has two asymptotes parallel to the x-axis. Preferably it should also only cross the x-axis at (0,0) and be built without using any trigonometric functions. Mind you, if ...
2
votes
2answers
33 views

When number of primes of the form $3k+1$ and $3k-1$ are the same

Let's denote the number of prime numbers of the form $3k+1$ which are not greater than $x$ with $\pi _{3k+1}(x)$. Similarly let's denote the number of prime numbers of the form $3k-1$ which are not ...
1
vote
0answers
20 views

Step in using Stirling's formula to get an upper bound

I'm having trouble seeing why the following holds. Given the conditions that $N=\binom{n}{2}$ and $m$ is a function of $n$ such that $N-m \to \infty$ as $n \to \infty$, why is it that $$(1+o(1)) ...
3
votes
0answers
63 views

Asymptotics of the solution of $G_n(t) = \text{const}$, where $G_n(t) = e^t (1 + r^{-1}(G_{n-1}(t) - 1))^{r}$.

Consider a sequence of functions $(G_n(t))$ on $\Bbb{R}$ that satisfies the recurrence relation $$ G_0(t) = e^t, \qquad G_n(t) = e^t \left( 1 + \frac{G_{s-1}(t) - 1}{r} \right)^{r}. $$ for some ...
3
votes
3answers
49 views

Solving recurrence $T(n) = T(n-2) +2 \log(n)$ using the Substitution Method

$T(n) = T(n-2) +2 \log(n)$ if n>1 & 1 if n=1 So I start by substituting 3 times to get an idea about the pattern: $T(n)=T(n-4) + 2 \log(n-2) + 2 \log n$ $T(n)=T(n-6) + 2\log(n-4) + 2\log(n-2) + ...
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 ...
0
votes
0answers
23 views

Proof Verification: Show that $n\mathrm{log}(n) \in O(\mathrm{log}(n!)$

I was wondering if my attempt in providing a proof of the above proposition holds. In proving that $n\mathrm{log}(n) \in O(\mathrm{log}(n!)$ I will equivalently prove that $\mathrm{log}(n!) \in ...
2
votes
0answers
57 views

Calculus book with big/ little oh

Is there an introductory calculus textbook out there that makes good use of big/ little oh notation? Things like defining the derivative $f'(a)$ as the number such that $$f(a+\epsilon) = f(a) + ...