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
20 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
31 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 ...
2
votes
0answers
25 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 ...
4
votes
2answers
299 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
6 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
28 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
16 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
30 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 ...
0
votes
1answer
28 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
59 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
49 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
48 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
122 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
28 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
18 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
33 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
61 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} ...
0
votes
0answers
30 views

Find the best Big-O estimate

Find the best (i.e., lowest) big-O estimate for the following function: $f(n) = 1 + 3 + 5 + 7 + ...+ (2n-1)$ Since the sum would be $f(n)= \frac{1 + n(2n-1)}2$, that would leave $\frac {2n^2 -n ...
15
votes
3answers
538 views

Can a function “grow too fast” to be real analytic?

Does there exist a continuous function $\: f : \mathbf{R} \to \mathbf{R} \:$ such that for all real analytic functions $\: g : \mathbf{R} \to \mathbf{R} \:$, for all real numbers $x$, there exists ...
-1
votes
0answers
22 views

For $\Theta$ notation which statements are true? [on hold]

Assume an algorithm runs in $\Theta(n^2)$, then which one of the following asymptotic notation for it? $O(n^3)$ $O(n^2)$ $\Omega(n^2)$ All above are correct.
0
votes
1answer
152 views

asymptotic sequence

I am asked to prove that $x^n(a+\cos(x^{-n})$ is an asymptotic sequence for $n=0,1,2,...$, $a>1$, $x\rightarrow 0$ but its derivative wrt x isn't an asymptotic sequence. ...
0
votes
3answers
52 views

Is $n^\frac{1}{10} \in O((\log n)^{10})$?

This question came up in a recent discussion: is $n^\frac{1}{10} \in O((\log n)^{10})$? First time I've come across a power of a log in a long time, and as far as I recall, there are no identities ...
1
vote
1answer
41 views

$N$ is approximately linear in $d$ for $N^d=\frac12 e^{N}$

let us look at the function $N^d e^{-N}$, for each $d\in \mathbb{N}$. The graphs of the function for various values of $d$ show a striking phenomenon: the graph look parallel, and with a near-constant ...
0
votes
1answer
22 views

Big O Notation asymptotic relationship

I cannot prove correctness/incorrectness of the implication of two functions f(n) and g(n) in Big-Oh/asymptotic notation $$g(n) = \Omega(f(n)) ) \implies g(n) = O(n^2f(n))$$ I believe $g(n) = ...
0
votes
0answers
12 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
0answers
12 views

Renormalization Group

I am studying singular perturbation technique right now. Can anyone suggest introductory books on singular perturbation using renormalization group method? I have several books on perturbation theory ...
1
vote
1answer
39 views

Why does $\frac{\frac12 x+\frac18x^2+O(x^3)}{\frac12x-\frac18x^2+O(x^3)}=1+\frac12x+O(x^2)$?

I was reading the solution to a limit through Taylor expansion but did not understand this passage: $$g(x)=\frac{1-\sqrt{1-x}}{\sqrt{1+x}-1}=\frac{\frac12 ...
1
vote
4answers
54 views

How to check if $n!$ is $ O(2^n)$

How can I check if $n! \in O(2^n)$? The definition of $f$ being $O(g)$ is $f(n) \le c g (n)$, where $c>0$. So it would mean $n! \le c 2^n$. What is the clearest way to solve this? (As I am ...
1
vote
1answer
24 views

For what maximum positive $k$ is $2n \sin^{2} \frac{\pi}{n} > \tan \frac{k\pi}{n}$ true?

I am trying to find the maximum value of $k$ such that the inequality $$2n \sin^{2} \frac{\pi}{n} > \tan \frac{k\pi}{n}$$ is satisfied. I impose restrictions that $n \in \mathbb{Z}$ with $n \geq ...
4
votes
1answer
77 views

Does “the functions agree at infinity” mean anything?

I want a way to describe how two continuous functions $f,g \colon (X-x) \to Y$ might "share a limit" at the point $x$ when unfortunately neither of $\displaystyle \lim _{y \to x}f(x)$ or ...
31
votes
6answers
668 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
27 views

Average of numbers converges, then what happens to the maximum

Let $\{a_n\}$ be a positive sequence of numbers such that $\displaystyle \frac1n\sum_{i=1}^n a_i \to a$ where $a>0$. Then can we say anything about the order of $\displaystyle b_n=\max_{i\in n} ...
-1
votes
0answers
11 views

Is f(n1 x n2) = Θg( n1 x n2 ) true?(Discrete mathematics, Algorithm)

I have a question about Theta Notation. For X={1,2,3 .....} n1 and n2 are elements of X If f(n1) = Θg(n1) and f(n2) =Θg(n2), then is f(n1 x n2) = Θg(n1 x n2 ) true? My speculation is that for n1 x n2 ...
4
votes
3answers
70 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
0answers
34 views

10-Subset Sum: Given a set of integers K and an integer M, is there a subset of exactly 10 elements of K whose sum equals M?

I understand that the more general Subset Sum problem is NP-complete, but I am under the assumption that this more specific version of the problem can be solved in polynomial time. However, I can't ...
0
votes
2answers
68 views

Approximation of a quotient that involves the Lambert function.

I would like to find an asymptotic upper bound for $$\frac{-\ln n}{W(- \ln^{-c}n)}$$ where $c$ is positive and $W$ is the Lambert function. More precisely, I want something which dominates this ...
4
votes
0answers
29 views

More elegant derivation of the shift in median bin occupancy

In answering Median of a multinomial variable, I found to my own surprise through a somewhat tedious calculation that the expected value of the median of the ball counts in $3$ bins into which $n$ ...
0
votes
1answer
33 views

Function $(2.2)^n$ — what is it?

The running time of an algorithms is $(2.2)^n$. I have to tell what is the maximum $n$ for reaching 1.000.000 steps. What type of a function is $(2.2)^n$? How its output depends on the input $n$? ...
2
votes
1answer
53 views

Asymptotic behavior of integrals of Legendre polynomials

By definition $\int_{-1}^1 |P_n(x)|^2 dx = O(n^{-1})$. What about the other powers? Do we know how $\int_{-1}^1 |P_n(x)|^k dx$ behaves for any $k$? Maybe $O(n^{-k/2})$?
0
votes
0answers
25 views

I am looking a comparison of this computation and Riemann's approach for $lcm(1,2\ldots,x)$

Looking a comparison with a reasoning due to Riemann, I ask to me about the behaviour as $x\to\infty$ of the following arithmetical function $$ \left( \prod_{n\leq x}n^{-\mu(n)}\right)\cdot \left( ...
1
vote
1answer
30 views

Asymptotic notation: What does $o(\epsilon_\text{mach})$ mean?

I'm having serious problems to understand what people mean when they write $o(\epsilon_\text{mach})$, where $\epsilon_\text{mach}$ stands for the machine epsilon. I'm seeing this in backward analysis ...
1
vote
0answers
14 views

Is $O(x^2)$ equal to OR a tighter bound for $O(x(x-y))$ if $x, y >0$ and $x>y$ alway hold?

In the question, $O$ is the Big-O notation, please see https://en.wikipedia.org/wiki/Big_O_notation. $x$ and $y$ are variables. Here, let me give you an example showing there exist such questions in ...
0
votes
1answer
43 views

Finding family of curve for given asymptotes

I need to find possible curves, with asymptotes given as $x=0 (x \to -\infty)$ and $y=mx \hspace{0.5cm} m>0$. it is easy to find curves for individual lines, $y= \exp(-\lambda_1 x) + mx$ for $y=mx$ ...
0
votes
2answers
34 views

Big O for a $\cos$ series

I have to show that $ \sum_1^N \cos(nx) = O(\frac 1{|x|}), [-\pi, \pi] $, x different from 0. I really don't know how to show that. I obviously know that $\cos(nx)$ is bounded by $1$, I know what ...
1
vote
0answers
30 views

Products of $k^{\mu(k)}$, where $\mu(n)$ is Möbius function, and the Prime Number Theorem

We can write $$e^{-\Lambda(n)}=\prod_{d\mid n}d^{\mu(d)},$$ where $\mu(n)$ is the Möbius function and thus $\Lambda(n)$ is von Mangoldt's function. Then taking the product from $1$ to $N$ we've for ...
0
votes
1answer
17 views

Simple Sigmoid function that levels off at specific points

I need to construct a simple Sigmoid function that levels off at specific values of x, as in this curve: What is the most simple Sigmoid function that I can use ...
-2
votes
5answers
95 views

Hello. I need to show that $\sqrt n$ grows faster than $(\log n)^{100}$ [closed]

Is there an easy way to show that $$\lim_{n\to \infty}\frac {(\log n)^{100}}{\sqrt n}=0 $$