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
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
136 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
275 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
543 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
71 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 ...
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 ...
0
votes
0answers
60 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 ...
2
votes
2answers
51 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$ ...
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
50 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) + ...
0
votes
0answers
24 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
59 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) + ...
2
votes
0answers
46 views

Asymptotic behavior of zeros of a function

Let $f(x,m)=(2m-1)\Gamma(m)\,x^{-m}$ where $x>0$ and $\Gamma(z)$ denotes the Gamma function. Let $g(x,m)=f(x,m)+f(x,-m)$. I'm interested in the solution $m=m(x)>0$ of the equation $g(x,m)=0$ ...
4
votes
0answers
73 views

Asymptotic Expansion for an Integral

So I have $$\psi(x)=\int_{2\lambda}^x \frac{(e\lambda)^{z}}{z^{z+1/2}} dz$$ I'm trying to find the asymptotic expansion of $\psi(x)$ as $x \to \infty$ for as many orders as possible. How would I go ...
5
votes
1answer
96 views

Weak convergence and convergence of moments

Consider a random variable $X$ defined on the probability space $(\Omega, \mathcal{F}, P)$ such that $X:\Omega\rightarrow \mathbb{R}$. Suppose that $X\sim N(\mu, \sigma^2)$. Consider a random ...
0
votes
1answer
37 views

Proving Gale-Shapley algorithm completes in $O(n^2)$

In Algorithm Design by John Kleinberg and Eva Tardos, the proof for the Gale-Shapley algorithm running in $O(n^2)$ is given In the case of the present algorithm, each iteration consists of some ...
0
votes
0answers
49 views

consider the function $f(1) = 1$, $f(n) = \sum_{i = 1}^{n - 1}(if(i))$ for $n > 1$

Consider the function $f(1) = 1$ $f(n) = \sum_{i = 1}^{n - 1}(if(i))$ for $n > 1$ Let $A(n)$ be the worst-case number of scalar arithmetic operations (+,-,*,/) required by this function for ...
1
vote
0answers
18 views

Can you discuss $\limsup_{n\to\infty}\frac{g_n}{\log^2p_n}\cdot\frac{\sigma(K_n)}{K_n\cdot\log\log K_n}$, where $g_n=p_{n+1}-p_n$ and $K_n\to\infty$?

Let $p_n$ the nth prime number, then we know that the nth gap is $g_n=p_{n+1}-p_n$. We define for $n>1$, $C_n$ as the set of integers such that $gcd(k,p_{n+1})=gcd(k,p_{n})=1$, this is $\{1\leq k ...
4
votes
3answers
88 views

Asymptotic formula for $\prod_{k=1}^{\infty}\zeta (2kn)$

Suppose $n\geq 1$ is a positive integer. Can we find an asymptotic formula for this product below. $$\prod_{k=1}^{\infty}\zeta (2kn)=\zeta (2n)\zeta (4n)\zeta (6n) \cdots$$ I tried to use $\zeta ...
1
vote
1answer
23 views

Give a big-O estimate of $(x+1)\mathrm{log}(x^2+1) + 3x^2$

I wanted to know if the following solution demonstrates that the function $f(x) = (x+1)\mathrm{log}\, (x^2+1) + 3x^2 \in O(x^2)$, because my answer and the book's answer deviate slightly. Clearly, ...
1
vote
1answer
42 views

What is the order of the quantifiers in the definition of big-O?

Suppose $f$ and $g$ are functions. I am pretty sure that the definition of big-O has its definition conform to the following logical structure $$\exists \, k \, \exists C \, \forall \,x\, :\, x > ...
0
votes
0answers
23 views

Questions about $w(\prod_{k=1}^{n}(p_{k}-1))-w(\prod_{k=1}^{n}(p_{k}+1))$

Let's define this functions. $$f(n)=\prod_{k=1}^{n}(p_{k}-1)$$ $$g(n)=\prod_{k=1}^{n}(p_{k}+1)$$ $$h(n)=\mid w(f(n))-w(g(n))\mid $$ where $p_{k}$ is $k$th prime number and $w(n)$ gives the number of ...
0
votes
2answers
42 views

Errors in our estimation of a function- and what does big-O notation have to do with it?

We're given the function $f(x) =e^x$ and we're trying to estimate its second derivative at $x=0$. Here's the estimation formula. $$f''(x)\approx {f(x) - 2f(x+h) + f(x+2h)\over h^2}= P(x)$$ All three ...
1
vote
0answers
29 views

How many binary polynomials of degree <2n-1 are the the product of polynomials of degree <n?

Let $P_n$ be the set of all polynomials over $\mathbb{Z}_2$ and of degree less than $n$. What is the rate of growth of $|\{x y : x,y \in P_n \}|$? I'm looking for an answer like "$\Theta(2^{3n/2})$" ...
2
votes
2answers
43 views

Big O - equivalent definitions

A function $f(x)$ is $O(g(x))$ if and only if there exists a real number $M$ such that there exists $x_0$ such that for every $x>x_0$ the inequality $|f(x)|\le M|g(x)|$. It turns out the following ...
4
votes
4answers
164 views

How to show $\zeta (1+\frac{1}{n})\sim n$

How to show $\zeta (1+\frac{1}{n})\sim n$ as $n\rightarrow \infty$ where $\zeta$ is the Riemann zeta function. And can we say $\lceil \zeta (1+\frac{1}{n}) \rceil=n$ for any positive integer $n\geq ...
0
votes
0answers
31 views

Define $T(2^n) = T(2^n/n) + 1$ with $T(1) = 1$ . Is $T(2^n)∈ Θ(n) ?$

I'm trying to solve the following problem $:$ Define $T(2^n) = T(2^n/n) + 1$ with $T(1) = 1$ . Is $T(2^n)∈ Θ(n) ?$ If I convert this recurrence relation into $:$ Define $T(k) = T(k/log_2k) ...
9
votes
1answer
128 views

Given the first $n$ primes, find the least common multiple of $p_1 - 1$, $p_2 - 1$, …, $p_n - 1$

Given the first $n$ primes, we can label the $k$th prime as $p_k$. So, what is the least common multiple(LCM) of {$p_1 - 1$, $p_2 - 1$, $p_3 - 1$, ..., $p_n-1$}? In other words, if we subtract $1$ ...
1
vote
0answers
40 views

Book Recommendations on Perturbation Theory

I am interested in studying Quantum Electrodynamics and figure I should begin by learning Perturbation theory and Asymptotic expansions. If anyone could recommend some books, that would be very ...
1
vote
1answer
52 views

Can I say $\log{O(n)}$?

Suppose $e^{f(x)} = O(x)$, or equivalently, there exists a $c$ such that for all $x$, $f(x) \lt \ \log{x} + c$. Is $f(x) = \log{O(x)}$ generally understood to mean the same thing?
0
votes
2answers
45 views

Finding the least integer n for a function Big-O of another function?

I was out all last week sick with the flu and am trying to get caught up in my Discrete Mathematics course. One set of questions in my book goes as follows: Find the least integer $n$ such that $f(x) ...
0
votes
0answers
20 views

It is possible an application of Shapiro's Tauberian theorem for $\sum_{n\leq x}\frac{|M(n)|^{1+\alpha}}{\pi(n)^{1+\beta}}\left[\frac{x}{n}\right]$?

I would like to know if I can find some $\alpha,\beta\geq 0$ such that defining the sequence $a(1)=1$ and for $n>1$ as $$a(n)=\frac{|M(n)|^{1+\alpha}}{\pi(n)^{1+\beta}},$$ where $M(n)=\sum_{k\leq ...
0
votes
0answers
20 views

Big-O Notation and showing algorithmic growth rate with witnesses?

I have been out of class sick for a week with the flu and am having some trouble getting caught up on our latest sections on Big-O notation. Can someone explain the following from the textbook to me? ...
9
votes
3answers
205 views

Finding where the tail starts for a probability distribution, from its generating function

Suppose we generate "random strings" over an $m$-letter alphabet, and look for the first occurrence of $k$ consecutive identical digits. I was with some effort able to find that the random variable ...
4
votes
1answer
393 views

Asymptotic error of Fourier series partial sum of sawtooth function

In Iwaniec's book, Topics in Classical Automorphic Forms, pg. 4, he gives the statement: $$\{x\}=\frac{1}{2}-\sum_{n=1}^N\frac{\sin 2\pi nx}{\pi n}+O((1+||x||N)^{-1})$$ where $\{x\}$ denotes the ...