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
1answer
37 views

When is a balance assumption consistent?

From Asymptotic analysis and perturbation theory by Paulsen: Find the behavior of the function defined implicitly by $$x^2+xy-y^3=0$$ as $x\to\infty$. [...] The final case to try is to ...
5
votes
1answer
816 views

Can a curve be an asymptote?

$f(x)=x^3+\frac{3}{x-1}$ This was the question given to me. I replied that $f(x)$ will have only a single vertical asymptote of $x=1$. My teacher told that there'll be be two asymptotes. One is the ...
0
votes
0answers
31 views

Asymptotics of a mean of exponential terms involving Gaussians

Let $X\sim \mathcal{N}(0,I_p)$ and $\tau=\sqrt{(2-\varepsilon)\log p}$ and $\varepsilon>0$. I want to prove that for sufficiently small $\varepsilon>0$ the following holds: $$ \mathbb{E}\left[ ...
1
vote
1answer
30 views

Asymptotic analysis references

I'm self studying asymptotic analysis with Bruijn (1981) - Asymptotic Methods in Analysis Bleistein and Handelsman (1986) - Asymptotic Expansions of Integrals but the texts are terse, without too ...
31
votes
5answers
713 views

A disease spreading through a triangular population

I have run into this problem in my research, which I'm presenting under a different guise to avoid going into unnecessary background. Consider a population that is connected in a triangular manner, ...
0
votes
1answer
13 views

Big O of a difference

Assume $f,g$ are such that $$\lim\limits_{n\to\infty}\frac{f(n)}{g(n)}=r\in\mathbb{R}.$$ Is there anything non-trivial we can infer about $$\left|\frac{f}{g}-r\right|$$ in terms of big-O notation, ...
1
vote
0answers
17 views

Trying to find the asymptotic behaviour of an inequality involving integers

Let $m,q,v$ be integers with $m\geq 2$, and $v|q-1$. A certain result that I have which is not important for this question, holds when $$q^{\frac{m}{2}-2}(q-mv)\geq v^{m-1}. \quad (1)$$ I would like ...
2
votes
1answer
82 views

Why is $\varepsilon x^5 \sim -x$?

I'm trying to understand what's going on in this lecture on perturbation (the link brings you to 1h 08m 12s). The original problem is to find the real root of $$x^5+x=1.$$ We have inserted ...
2
votes
0answers
51 views

What's about $\sum_{n=1}^{\infty} \frac{e^{H_n}\log H_n}{n^3}$, where $H_n$ is the nth harmonic number?

I would like to do a toy verification of the Riemann hypothesis exploiting theLagarias theorem (see the section Applications in the following link) and the fact that we know a lot of decimals for ...
4
votes
0answers
84 views

A conjectured asymptotic expansion of a function related to the sine and cosine integrals

Recall the definitions of the sine and cosine integrals:$$\operatorname{Si}(x)=\int_0^x\frac{\sin t}t dt,\quad\operatorname{si}(x)=-\int_x^\infty\frac{\sin t}t ...
4
votes
1answer
41 views

Proving recurrence relation with induction: $T(n) = T(n-1) + n$

I have to prove that the bound of the following relation is $\theta(n^2)$ by induction- $$T(n) = T(n-1) + n$$ should i seprate my induction into two sections - to claim that $T(n) = O(n^2)$ and ...
7
votes
3answers
181 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 ...
3
votes
2answers
45 views

Minimize a particular function in one variable

For given $a,b$, what is the minimum value of the following expression? $$ \frac{a}{x^2+b}+x,\qquad x>=0, a>0,b>0 $$ Differentiating the above gives a messy polynomial. I tried plugging ...
0
votes
2answers
33 views

Can we Relate Radius of Convergence of Taylor Series and Asymptotic Rate of Growth?

I still need to be disabused of the belief that there is some simple connection between the finiteness of the radius of convergence and the asymptotic rate of growth. 1. Can we develop any ...
0
votes
1answer
58 views

What is the pattern of the Stirling series?

It can be shown that: \begin{eqnarray*} n! = \left ( \frac{n}{e} \right )^n \sqrt{2 \pi n} e^{ \frac{B_2}{2n} + \frac{B_4}{4 \cdot 3 \cdot n^3} + \cdots + \frac{B_{2m}}{2 m ( 2m-1) ...
1
vote
1answer
20 views

Is Every (Real) Analytic Function (with Non-Degenerate MacLaurin Series) Asymptotically Greater Than any Polynomial?

Question: Given a function $f: \mathbb{R} \to \mathbb{R}$ such that the MacLaurin series exists and equals the function for every $x \in \mathbb{R}$, and such that for all $n \ge n_0$, $n_0$ some ...
1
vote
3answers
125 views

Calculating Running Time (in seconds) of algorithms of a given complexity

I've tried to find answers on this but a lot of the questions seem focused on finding out the time complexity in Big O notation, I want to find the actual time. I was wondering how to find the ...
1
vote
0answers
38 views

Upper-bounding $\sum_{i=1}^n \sum_{j = i}^{i+a_i} \frac{1}{\sqrt{j}}$?

Suppose $a_1, ..., a_n \in \mathbb{N}$ are arbitrary integers. Is it possible to bound $$ A =\sum_{i=1}^n \sum_{j = i}^{i+a_i} \frac{1}{\sqrt{j}} $$ with either of the following: $$ B = ...
1
vote
2answers
32 views

Is it true that $ \sum_{i=1}^m \frac{1}{\sqrt{i}} = O \left( \sqrt{ m-1 } \right) $?

Is it true that?: $$ \sum_{i=n}^m \frac{1}{\sqrt{i}} = O \left( \sqrt{ \frac{m-n}{n}} \right) $$ In special case if we have $n = 1$, is it true that?: $$ \sum_{i=1}^m \frac{1}{\sqrt{i}} = O \left( ...
0
votes
1answer
65 views

Upper bound on $(1 + x)^n$

I'm looking for a useful upper bound on $(1 + x)^n$ in terms of $n$ and $x$. You can assume $x > 0$. Does anyone know one? An asymptotic upper bound would also be helpful.
1
vote
0answers
38 views

Can you get the average order of $ \left( 1+|\mu(n)| \right)^{M(n)} $, where $\mu(n)$ and $M(n)$ are the Möbius and Mertens functions, respectively

When yesterday I was interested in do a little study about the arithmetic function $$f(n)=\left( 1+|\mu(n)| \right)^{M(n)},$$ defined for integers $n\geq 1$, which $\mu(n)$ is the Möbius function and ...
0
votes
1answer
25 views

On a bound about $\sum_{n\leq n}\sqrt{\frac{x}{n}} \left[\sqrt{\frac{n}{x}} M \left(\frac{x}{n} \right) \right] $

From the fact that $f(x)= \left[f( x) \right]+ \left\{ f(x) \right\} $, where $ \left\{ x \right\} $ is the fractional part function, one can write by a direct substitution for the function ...
0
votes
1answer
7 views

Time complexity of modulo scenario

Something theoretical here. Say if I have two natural numbers $x$ and $y$. Both these numbers are upper-bounded by a third number $z$. ($O$($z$)) Now let's say I have a recursive modulo function ...
0
votes
0answers
20 views

How do I determine values of b, so the difference equation (*) becomes global asymptotic stable?

The difference equation in the picture down below is marked with (*): I don't know where to start. In which direction should I be looking at? I tried to start looking at the characteristic ...
1
vote
0answers
37 views

Why is $\frac{1}{1-x} = 1 + \Theta(x)$ for $x \in (0,1)$?

I am trying to understand the statement $$ \frac{1}{1-x} = 1 + \Theta(x) $$ for $0 < x < 1$. To my understanding, this could mean two things: There are constants $C_1$ and $C_2$ such that ...
0
votes
1answer
23 views

Discrete Math Big O Notations

I'm studying for my discrete math class and I don't fully understand how to proof how a function is not a big O for certain questions. I understand that you have to assume that it is big O and proof ...
0
votes
1answer
34 views

Limit of triple sum

Suppose one has the following triple sum: $$S_n=\sum_{s=0}^n\sum_{t=0}^s\sum_{u=0}^sf(n,t)g(n,u)$$ where for all $n$, $-\alpha< S_n <\alpha$ for some real constant $\alpha<\infty$. Since ...
-1
votes
2answers
47 views

Using the definition of $f$ is $O(g)$ proof:

I'm studying for my discrete math class and I don't understand how to prove big O notation. I understand that $f$ is $O(g)$ of another if $f(x) \le c g(x)$ holds. How would I go about proving $\sin ...
2
votes
0answers
42 views

Uniform approximation. Two boundary layers?

Find uniform approximation up to order $O(\epsilon)$: $$ \begin{cases} \epsilon y''+\epsilon y' - y^2=-1-x^2 \\ y(0)=2 \\ y(1)=2 \end{cases} $$ At $\epsilon=0$ solutions $\pm \sqrt{1+x^2}$ don't ...
0
votes
0answers
15 views

Comparing two functions asymptotically

I have been given this question: Indicate whether $f=O(g)$, or $f=\Theta(g)$, or $f=\Omega(g)$. Justify your answer and show all your work. $f(n) = n3^n$ $g(n) = 500n + 10$ I can see ...
1
vote
0answers
20 views

Maximum of twisted binomial coefficients

For any integer $n$, define $$\mu(n)=\text{arg max}_{1\leq k\leq n}\binom{\frac{n+k}{2}}{k},$$ where the binomial coefficients are set to $0$ if $n+k$ is odd. Question: Is the sequence ...
0
votes
1answer
28 views

Solve $T(n)=2T(n/2)+\log n$ with $T(1)=1$

Solve$$\begin{cases}T(n)=2T(n/2)+\log n\\ T(1)=1\end{cases}$$ I tried to use the master theorem but it didn't work, so I used the trees methode ...
1
vote
1answer
41 views

Asymptotic approximation of $\int_1^x(1+t^{-1})^tdt$ for $x>1$

I'm self-studying Bruijn (1961)'s Asymptotic Methods in Analysis. Below is the first exercise of Chapter 1. Show that $$ \int_1^x(1+t^{-1})^tdt=ex-\frac{1}{2}e\log x+O(1)\quad(x>1). $$ The ...
4
votes
2answers
304 views

Series about Euler-Maclaurin formula

The Euler-Maclaurin formula says (from Concrete Mathematics section 9.5) \[ \sum_{a\le{}k< b}f(k)=\int_a^bf(x)dx+\left.\sum_{k=1}^m\frac{B_k}{k!}f^{(k-1)}(x)\right|_a^b+R_m \] where ...
0
votes
0answers
10 views

Are these asymptotic relations correct?

In this thread, user proves, that for positive $f(n)$ and $g(n)$, following holds: $\max(f(n), g(n)) = \Theta(f(n) + g(n))$ With whatever basic understanding I have about asymptotic ...
1
vote
0answers
32 views

Limit of monotone decreasing function on generalised inverse.

Consider a right-continuous, monotone decreasing, non-negative function $\bar F(x)$ (its the tail of a probability distribution, but that doesn't matter). Now let \begin{equation} I_{n}=\{x : \bar ...
0
votes
1answer
18 views

Determing stretching variable in inner expansion of boundary layer problem

I am studying perturbation theory, and I have a problem when reading the book "Introduction to Perturbation Methods" by M.H. Holmes. This is about boundary layer. We know when seeking inner expansion, ...
0
votes
0answers
16 views

Question about asympotic behavior of $\frac{1}{s}\int_0^s u(x,t) dt$ .

I am just reading a paper, in the final theorem, the author wants to prove that $u(x,t)$ converges to some $v(x)$ in the $L^2$ norm as $t$ $\to$ $\infty$. But in the proof, he defines a ...
1
vote
0answers
33 views

Why should $\phi'$ and $\phi''$ be $\mathcal O(1)$?

As Strogatz writes in his book Nonlinear Dynamics And Chaos (p. 64) There are often several ways to nondimensionalize an equation, and the best choice might not be clear at first. Therefore we ...
-1
votes
1answer
35 views

Why is this big oh $O(n^3)$

Why is this big oh $O(n^3)$? (b) Give a good big-Oh bound on the function $$f(n)=2^{\log_2 n} n^2 + 3n^2 \log_2 n +n -17$$ I am not sure on how to solve this. If someone could help me solve, I ...
0
votes
4answers
62 views

Trying to solve recurrence $T(n)=3T(n/3) + 3$

I'm trying to solve the following recurrence without using the Master Theorem: $$T(1)=1;$$ $$T(n)=3T(n/3) + 3$$ My attempt: $T(n) = 3T(n/3) + 3$ $ = 3(3T(n/9) n/3)) + 3)$ $ = 9T(n/9) + 9$ $ = ...
-2
votes
0answers
56 views

What are the Correct Conditions for Akra-Bazzi Master Theorem?

The Akra-Bazzi method solves recurrences of the form: $$T(n) = g(n) + \sum\limits_{i=1}^k a_iT(b_in + h_i(n))$$ In the Wikipedia article about the topic, it says that the condition on $g(n)$ is: ...
0
votes
0answers
53 views

What explains this repeating pattern in the difference between a Riemann zeta zero related sequence and its conjectured asymptotic?

As the starting point for my experiment I assumed that the imaginary parts of the Riemann zeta zeros are of the form: $$\Im \{ \rho_n \} = \frac{2\pi}{\log x_n}$$ where $x_n$ is unknown. Therefore I ...
3
votes
2answers
124 views

Asymptotics of the differences between successive zeta zeros

Does anyone know what the asymptotic of the differences between successive zeta zeros is? Update It appears that $\zeta(n)$ is not a bad asymptotic, when the data range is stretched: ...
3
votes
1answer
29 views

Prove $O(f(n)+g(n)) = O(f(n))$ when $g(n)=O(f(n))$

Given $g(n) = O(f (n))$, how can I prove that the following expression is true: $O(f (n) + g(n)) = O(f (n)) \tag1$ So I just write down what it says: $g(n) = O(f (n)) <=> f(n) \le c_1 ...
1
vote
0answers
29 views

Finding the inverse of a function involving logarithms

Let $A \asymp B$ mean that there exists universal constants $m,M >0$ such that $mA \leq B \leq MA$. Let $k,n \in \mathbb{N}$ be such that $\log n \leq k \leq n$. I want to prove that $$ k ...
2
votes
2answers
20 views

Asymptotic upperbound in multiplication

How can someone calculate the asymptotic upperbound of $2^nn^2$? The first term ($2^n$) grows much faster than the second, but saying that as a final result $2^nn^2 = O(2^n)$ would only be true in the ...
1
vote
1answer
36 views

What is the asymptotic behavior of this integral?

The function $F(x)$ is defined by the following integral $$F(x)=\int_0^x\frac{\left(1-y^3\right)^a}{\sqrt{\left(\dfrac{1-y^3}{1-x^3}\right)^b-\left(\dfrac{y}{x}\right)^4}}\,dy$$ where $a$ and $b$ ...
2
votes
0answers
16 views

Find Theta Class of T(n) = T(3n/4) + T(n/6) +5n [duplicate]

I'm not quite sure I can apply the Master Theorem to T(n) = T(3n/4) + T(n/6) + 5n. It is not in the normal form of T(n) = aT(n/b) + f(n). Is it possible to apply the MT to it? If not, can the ...
1
vote
1answer
67 views

A sum of Stirling numbers of the second kind

Find a formula (either exact or asymptotic in $N$) for $S(N)$, where \begin{equation} S(N) = \sum_{n=N}^\infty \sum_{k=N}^n \sum_{j=0}^k \binom{k}{j} (-1)^{k-j} (1+j)^n \frac{t^n}{n!}. \end{equation} ...