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

learn more… | top users | synonyms (1)

3
votes
2answers
47 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
35 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
59 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
140 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 = c\sqrt{\sum_{...
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
41 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 $M(x)=\...
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 equation:...
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 $1+...
-1
votes
1answer
26 views

Discrete Math Big O Notations [closed]

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 $...
2
votes
0answers
44 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 $\left(\mu(n)\...
1
vote
1answer
44 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
305 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
12 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 F(x)...
0
votes
1answer
21 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 $w(x,s)=\frac{...
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
36 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
63 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$ $ = ...
3
votes
2answers
127 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 g(n)...
1
vote
0answers
30 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 \log(\...
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
37 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
17 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
69 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
35 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
551 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 ...
0
votes
1answer
154 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. https://www....
0
votes
3answers
53 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
42 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
25 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) = \Omega(...
0
votes
0answers
13 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 x+\frac18x^2+O(x^3)}{\frac12x-\frac18x^2+O(...
1
vote
4answers
56 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 5$...
4
votes
1answer
78 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 $\...
0
votes
1answer
29 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} a_i$...
4
votes
3answers
73 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
40 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
74 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 ...
5
votes
0answers
35 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$ ...