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
2answers
28 views

comparing functions in big O notation

I am extremely new a calculating big O notation and I am extremely confused by this quote from the book Discrete Mathematics and Its Applications For instance, if we have two algorithms for solving ...
0
votes
1answer
62 views

Using the master theorem to find an upper bound for $T$, where $T(x) \leq 4 T(\left \lfloor{\frac{x}{2}} \right \rfloor) + x$

Let $x \in \mathbb{N}$. We have the relation: $T(x) \leq 4 T(\left \lfloor{\frac{x}{2}} \right \rfloor) + x$. I am trying to find an upper bound for $T$. if $x$ is a power of $2$ i.e. $x = 2^n$. I ...
7
votes
5answers
4k views

Simple proof of showing the Harmonic number $H_n = \Theta (\log n)$

Consider the partial sum of the divergent Harmonic series $H_n = \sum\limits_{k = 1}^{n}\frac{1}{k}$. I recently saw a question which required finding out the asymptotic bounds of $H_n$. Now, I could ...
0
votes
1answer
20 views

Asymptotic complexity of power of logs

I'm trying to simplify $\Theta(lg^k(n/2))$. I believe it's $\Theta(lg^kn)$ but i don't know if the following proof is correct... i'd love to receive some input I tried doing - ...
2
votes
1answer
41 views

If $\lim_{n\to\infty}\frac{\ell_n}{\log n}=1$, does $n\log n\geq -C \iff (n+1)\ell_{n-1}\geq -C$ hold? [closed]

Let $\ell_n:=\sum_{k=0}^{n}\frac{1}{k+1}.$ It is known that $\ell_n\sim\log n.$ i.e $\lim_{n\to\infty}\frac{\ell_n}{\log n}=1.$ Then, for $C\geq 0$ it is possible that $n\log n\geq -C \iff ...
3
votes
2answers
49 views

Asymptotic complexity of sum of poly-logarithmic functions

I'm trying to figure out what's the asymptotic complexity for the following sums: $$\sum_{k=1}^n lg^s k$$ $$\sum_{k=1}^n k^rlg^s k$$ s and r are positive constants. I think i should be using ...
0
votes
0answers
15 views

Are integrals over sequences of functions asymptotic equivalent?

i have given a sequence of functions $(f_{n}(x))_{n>0} $ for which the following holds pointwise : $ \lim_{n \to \infty} \frac{f_{n}(x)}{g_{n}(x)}=1$. Does then also hold: $\lim _{n \to \infty} ...
2
votes
1answer
92 views

What is the growth rate of $a_{n+1} = a_n^2 + 1$?

Let $a_1 = 1$, and let $a_{n+1} = \left(a_n\right)^2 + 1$. What is the growth rate of $a_n$? Even better, is there a closed-form formula for $a_n$? Since each step is "basically squared", I'd ...
2
votes
1answer
82 views

Boundary value problem with rescaling

Consider the boundary value problem $$\varepsilon \frac{d^2y}{dx^2}+(1+x)\frac{dy}{dx}+y=0$$ subject to $y(0)=0$, $y(1)=1$, for $0 \leq x \leq 1$. By considering the rescaling $x=x_0+\varepsilon ...
1
vote
1answer
31 views

Show that $\exp(x)-1=\mathcal{O}(x)$ for $x\to 0$

Find a function $g(x)$ that is as simple as possible s.t. $\exp(x)-1=\mathcal{O}(g(x))$ for $x\to 0$. Claim. Such a possible function is $g(x)=x$. Proof. Using the definition of the class ...
0
votes
0answers
16 views

Proving a recurrence's $\Theta$ with induction

Prove with induction that $T(n)=T(\frac n 2)+\log n = \Theta (n^2)$ Starting with the big $O$, the basis $T(2)\le c 2^2$ is obvious. Assume it's true for $n$ and prove for $n+1$: $T(n)=T(\frac n ...
0
votes
0answers
23 views

What is the Edgeworth Expansion of the binomial distribution?

For a standardized binomial distributed random variable $\tilde B_n$ we have $$P(\tilde B_n\le x) = \Phi(x) + \frac {q-p}{6\sqrt{npq}} (1-x^2) \phi(x) + ...
0
votes
1answer
26 views

Little o notation - equivalence

I need to help with mathematical problem. Let's have function $g(n) : \mathbb{N} \to \mathbb{R}^+$ and $2$ sets defined: $$o(g(n)) = \{f(n) : \mathbb{N} \to \mathbb{R}^+\;|\; \forall c \in \mathbb{R}^ ...
1
vote
1answer
28 views

Show $\int_0^tK(s) e^{-k(t-s)} \text{d}s\approx K(t)\int_{-\infty}^t e^{-k(t-s)} \text{d}s$ using Watson's lemma

How can you show using Watson's lemma, that for some infinitely differentiable function $K(s)$ and $ kt \gg 1$ that $$\int_0^tK(s) e^{-k(t-s)} \text{d}s\approx K(t)\int_{-\infty}^t e^{-k(t-s)} ...
34
votes
1answer
1k 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 ...
2
votes
1answer
32 views

Asymptotic growth of products of powers of primes vs factorials

Suppose we are comparing products of powers of primes p vs. n!: p₁^(2n/p₁)∙p₂^(2n/p₂)∙p₃^(2n/p₃)∙p₄^(2n/p₄)∙... vs. n! If ...
0
votes
2answers
44 views

Why is $\frac {x^2 + 1} {x + 1}$ in $O(x)$?

For me I $\dfrac {x^2+ 1} {x+1}$ by $x^2$ since that's the term with the highest exponent making it: $\dfrac {1 + \frac 1 {x^2}} {\frac 1 x + \frac 1 {x^2}}$ but I'm not sure where to go from there. ...
0
votes
1answer
95 views

How to check if a function is negligible?

Let $\epsilon(x)$ be a negligible function. Let $p$ be a polynomial such that $p(k) \geq 0$ for all $k > 0$. What can we say about $\epsilon(p(k))$? Is this a negligible function? If yes, ...
1
vote
4answers
43 views

Relation Big-O and limit of a function?

It is not clear to me what it the relationship (if any) between Big-O and limit of a function. Suppose that a function $f(x)=O(g(x))$: does this imply that $f(x)$ converges to a limit as $x\rightarrow ...
4
votes
0answers
27 views

Arnold's combinatorial description of entropy.

V.I. Arnold says that entropy is related to the asymptotic behaviour of polynomial coefficients. This is mentioned in his book "Dynamics, Statistics and Projective Geometry of Galois Fields". Here ...
0
votes
0answers
26 views

Method of stationary phase to evaluate an integral.

I need help showing that $$I(x) = \int_{0}^{\infty} \frac{1}{1+t}e^{ix\left(\frac{t^{3}}{3} -\frac{3t^{2}}{2} +2t\right)} dt \thicksim ...
1
vote
0answers
19 views

Asymptotic solutions to second order ODE

I don't understand the following argument in my lecture notes: Consider the following ODE: $$ w''(z) + f(z) w'(z) + g(z) w(z) = 0, \quad z \in \mathbb{C}$$ where $$f(z) = f_0 + ...
2
votes
1answer
91 views

Asymptotic standard normal distribution

I need to solve the following exercise. Assume that $X_\lambda$ is Poisson distributed with mean $\lambda$ . Show that $Y(\lambda) = \frac{X_\lambda - \lambda}{\sqrt{\lambda}}$ is asymptotic ...
3
votes
3answers
93 views

Estimating an exponential sum $\sum_{n = 1}^x e^n/n$

I'm interested in estimating the exponential sum $$ \sum_{n = 1}^x \frac{e^n}{n} $$ for reasonably large $x$. One way to try to understand this sum is to approximate it with an integral $$ ...
0
votes
1answer
44 views

How to solve harmonic oscillator-like equation with $\theta$-function?

Suppose second order linear differential equation $$ \frac{d^2 y(t)}{dt^2} + \omega^2(t)y(t) = 0, \quad \omega^2(t) = q^2 + \theta (t-t_{0})m^2 $$ ($\theta (t)$ denotes Heaviside step-function) with ...
6
votes
3answers
145 views

Arithmetic rules for big O notation, little o notation and so on…

There are many asymptotic notations like the big O notation: big Omega notation, little o notation, ... Thus there are many arithmetic rules for them. For example Donald Knuth states in Concrete ...
1
vote
2answers
39 views

Reference request for a notation stating absolute error

My Question: Let $\Delta(a_n)$ be defined by $$(a_n)\in \Delta(a_n)\iff \forall n\in\mathbb N: |\epsilon_n| \le |a_n|$$ I guess it is very likely that this notation is already used in mathematical ...
3
votes
3answers
69 views

Is $\log^2n = O(n)$ or $n = O(\log^2n)$ true?

I'm trying to figure out if: 1) $\log^2n = O(n)$ and 2) $ n = O(\log^2n)$ are true or if one or both are false. So far I've concluded that both are false because if $n = 8$ for the first one, then ...
0
votes
0answers
27 views

asymptotic equivalence

i have a question about asymptotic equivalence which means $ \lim_{n \to \infty} \frac{f(n)}{g(n)}=1$ with notation $f(n) \sim g(n)$. I know that the following holds: $\sum_{j=0}^{\infty} ...
0
votes
0answers
26 views

Big O notation and double “less than” notation

"Big O" notation crops up everywhere in analytic number theory. Roughly speaking, we say $f(x) = O(g(x)$ if there exists a positive constant $M$ s.t. $\lvert f(x) \rvert \leq M \lvert g(x) \rvert $ ...
1
vote
0answers
48 views

Watson's Lemma to obtain first three terms

I am unsure how to proceed with the following question due to the fact I am unsure how to obtain a Taylor series for the following function. Question: Using Watson’s Lemma, obtain the first three ...
1
vote
0answers
42 views

asymptotic expansion of exponential solution to ODE

Obtain the first two terms of the asymptotic (large x) solution for each of the 2 real solutions of $$u''+\left ( 1-\frac{\gamma}{x^{2}} \right )u=0$$ in $$x> 4$$ Now, For large x, the above ...
2
votes
0answers
21 views

Convergence in probability or convergence in distribution?

Let $X$ be a random variable. let \begin{align*} Y=\alpha_1+\alpha_2 X \end{align*} where $\alpha_1$ and $\alpha_2$ are parameters. Now let \begin{align*} Z=\hat{\alpha}_1+\hat{\alpha}_2 X ...
7
votes
0answers
136 views

An inequality for $|\zeta (s,a)|$, a detailed proof

In page 272 of [1], Apostol leaves as a reader's assigment to complete a proof of a related statement with Hurwitz zeta function, defined initially for $\sigma >1$ by the series ...
2
votes
2answers
68 views

Laplace's Method to verify an asymptotic approximation

Question: Using Laplace’s method, verify the following asymptotic approximations as $x \to \infty$ $$\int_0^\infty t^x e^{-t} \ln t \, dt \sim \left(\frac{2\pi}{x}\right)^{1/2} e^{-x}$$ I am ...
5
votes
2answers
73 views

Is it true that $ \sum_{t = 1}^T \frac{T-t}{ t+ \sqrt{T-t}} \in O(T) $?

Is the following true? $$ \sum_{t = 1}^T \frac{T-t}{ t+ \sqrt{T-t}} \in O(T) $$
1
vote
2answers
52 views

asymptotic expansion/approximation

Find the small solution of $$y''-y\left ( 1-y^{2} \right )=0 \text{ with } y\left ( 0 \right )=\epsilon \ll 1$$ Making a pun, I decided that $$y^{3}\left ( 0 \right )\ll y\left ( 0 \right )$$ so ...
2
votes
1answer
34 views

Iterated $\sigma^k(n)$, excluding the possibility that primes $p|\sigma^t(n)$, $t< k$ divides an odd perfect number $n$

Let $m\geq 1$ an integer and $\sigma(m)=\sum_{d|m}$ the sum of positive divisors function. A positive integer is said to be perfect if and only if $\sigma(n)=2n$. We have that $\sigma(m)$ is a ...
0
votes
2answers
19 views

Proving that two little $o$ definitions are equivalent

In 'Related notations' chapter: We write $f(x) = o(g(x))$ for $x \to a$ if and only if for every $C>0$ there exists a positive real number $d$ such that for all $x$ with $|x - a| < d$ we have ...
3
votes
1answer
87 views

Twin prime conjecture implies $\limsup_{n\to\infty}\frac{\sigma(n)\pi(n)}{n^2}\left(\pi(\log n)-\frac{\pi_2(\log n)}{2C_2}\right)=e^{\gamma}$?

Let $\sigma(n)$ the sum of positive divisor function, $\pi(x)$ is the prime counting function, $\pi_2(x)$ is the twin prime counting function (we will assume that Twin prime conjecture holds), $C_2$ ...
0
votes
1answer
44 views

Generalization of asymptotic notations like big O or little o notation

Context and question For a thesis I need to prove all the arithmetic rules for asymptotic notations – such as $O(\cdot)$ or $\omega(\cdot)$ – I have used (which are a lot). Currently I look for a ...
3
votes
0answers
42 views

Average Order of $\frac{1}{\mathrm{rad}(n)}$

Again a question about $\mathrm{rad}(n).$ Let $\mathrm{rad}(n)$ denote the radical of an integer $n$, which is the product of the distinct prime numbers dividing $n$. Or equivalently, ...
0
votes
0answers
42 views

Find smallest $k$ such that the given trigonometric functions are $O(x^k)$

I feel like I do not quite grasp the concept of Big O Notation. From my understanding, if $f(x) = O(g(x))$ then $f(x)$ is at most $g(x)$ multiplied by some constant C, which makes decent sense to me. ...
2
votes
1answer
26 views

A confusion about big Oh notation

As far as I know, the statement $|T|\le C_M\cdot (\log N)^{-1}.|\Omega|,\ (C_M>0)$ should imply that $$|\Omega|=\mathcal{\Omega}(|T|\log N)$$ but this seminal paper by Candes et al. says in the ...
0
votes
2answers
79 views

Proof by induction summation inequality: $\sum_{i=1}^n i^2 = O(n^3)$

show by induction that: $$\sum_{i=1}^n i^2 = O(n^3)$$ what I have so far: $$\sum_{i=1}^n i^2 \le n^3$$ base case: for n=1 $$\sum_{i=1}^1 i^2 \le 1^3$$ ...
2
votes
1answer
46 views

Show that $\frac{N}{m}((N+m)\ln(N+m)+(N-m)\ln(N-m)-2N\ln(N)) \to 1$ when $N\gg m$

$$\frac{N}{m^2}((N+m)\ln(N+m)+(N-m)\ln(N-m)-2N\ln(N))\to 1 \text{ when } N \gg m$$ I got this expression from fiddling around with Brownian motion. From inputing values for $N$ and $m$ I can see ...
2
votes
0answers
16 views

Big $O$ notation clarification

I've encountered something of the form: $$f(n)O(g(n))$$ I think this is equivalent to $O(g(n)f(n))$, but is this true?
0
votes
1answer
55 views

Is the asymptotic growth rate of the product of divisor function up to $n$ known?

Let $\tau(k)$ be the number of divisors of the positive integer $k.$ How does $f(n)\stackrel{\triangle}{=}\prod_{k\leq n} \tau(k)$ or a reasonable function of it,such as $\log f(n)$ or $f(n)^{1/n}$ ...
2
votes
2answers
325 views

Asymptotic behaviour of $\sum_{p\leq x} \frac{1}{p^2}$

As the title suggests, I want to find the asymptotic behaviour of this sum as $x\rightarrow \infty$, I tried by summation by parts but didn't succeed I also tried using the asymptotic behvaiour of the ...
0
votes
1answer
34 views

What does it mean to be less than a constant + $o(1)$?

Suppose $f:(0, \infty)\to\mathbf{R}$ is bounded (by $B$, say) and non-negative. Then $$l := \limsup_{x\to\infty} f(x)$$ exists. The proof I'm reading now claims that $f(x) \le l + o(1)$, which I'm ...