Questions involving asymptotic analysis, including growth of functions, Big-O notation, Big-Omega and Big-Theta notations.
5
votes
1answer
129 views
An estimate of a series
Suppose $s$ is not an integer, let $\lambda(s)=\min_{n≥0}|s+n|$. Show that $\sum\limits_{n=1}^{\infty}(\frac{1}{n+s}-\frac{1}{n})\ll\frac{1}{\lambda(s)}+\log(|s|+2)$.
3
votes
1answer
91 views
Techniques for asymptotic growth comparison between complicated expressions
For the following functions:
$$\frac{2^n}{n + n \log n}$$
and
$$4^{\sqrt{n}}$$
I'd like to compare their asymptotic growth as $n \to \infty$. Is there any other way to do that other than using ...
0
votes
1answer
50 views
Finding the limit of a summation in order to find Asymptotic Comlexity [duplicate]
I havent done this in a while so I was hoping someone can remind me how to do this,
I need to find the limit of this summation:
$$\lim_{n \to \infty}{\displaystyle\sum_{k=1}^{n} \frac{1}{k^2}} $$
...
-1
votes
1answer
137 views
How to find asymptotic entire functions?
I want to know how to find analytic functions $f(z)$ that are asymptotic and analytic on and near the real line of functions of the type $\ln(C +\exp(P(z^2)))$ where $C$ is a complex constant and $P$ ...
1
vote
1answer
102 views
Big o notation $( n \log n + n \log(n^{\log n}))$
I'm trying to transform this: $$n \log n + n \log(n^{\log n})$$ into big O notation.
I can't get to reduce the right part of the addition...
Neither of these work: $$n^{\log n} ...
0
votes
1answer
83 views
What does it mean when you say that the function is bounded?
What I figured is that it means that the function has an upper bound, however I came across this text:
Here since g(x) either equal or less to f(x), |g(x) / f(x)| must be bounded right? Since the ...
3
votes
1answer
74 views
BigO sorting complexity help
Given a bit sequence of length a, what is the minimum number of comparisons needed to determine if it contains a pair of consecutive 1's in BigO notation
2
votes
1answer
100 views
Lower bound for matrix sorting?
Consider the problem of sorting a $n$ by $n$ matrix i.e. the rows and columns are in ascending order. I want to find the lower and upper bound of this problem.
I found that it is $O(n^2logn)$ by just ...
5
votes
2answers
100 views
Estimating rate of blow up of an ODE
Suppose I have a differential equation $x'=f(x)$ and $f(x)>0$ grows super-linearly. I.e., $\lim_{|x| \rightarrow \infty} |f(x)|/|x| \rightarrow \infty$.
Several related questions: (1) Can I ...
4
votes
0answers
44 views
Asymptotic behavior of $|f'(x)|^n e^{-f(x)}$
Let $f$ be a strictly convex function on $\mathbb R$, $f'' \geq C > 0$. Let $n$ be a positive integer. What can we say about the growth rate of $|f'(x)|^n e^{-f(x)}$ as $x\rightarrow \infty$? Must ...
1
vote
1answer
47 views
Difficulty proving / disproving the following equalities relations ( Big Ω)
I have left with some functions I can't find witenesses for proving/disproving Big Ω equalities relations.
Here are the three relations:
$ \sum\limits_{i=1}^{n} (i^3 - i ^2) = \Omega(n^4) $
...
4
votes
2answers
276 views
Asymptotic approximation to incomplete elliptic integral of third kind at a pole - determine constant
while studying a physics problem I found that asymptotically the incomplete elliptic integral of the third kind, (using the Mathematica conventions, where it is called EllipticPi),
...
0
votes
2answers
105 views
Asymptotic upper bound in Big-O for $T(n)=T(n-1)+3n-5$. Proof using induction
I need to prove using induction Asymptotic upper bound in Big-O for
$$T(n)=T(n-1)+3n-5$$
So I tried expanding
$$\begin{align}
T(n) &= T(n-1) + 3n - 5 \\
&= T(n-2)+ 2(3n-5) \\
&= T(1) ...
2
votes
1answer
58 views
Prove $f(n)=n \log{\log{n}} \notin \Theta (n^k)$ for any $k$
How do I prove $f(n)=n \log{\log{n}} \notin \Theta (n^k)$ for any $k$? I have no idea where to start but I tried plotting the graph in Google and noticed that $\log{\log{n}}$ is very close to 0.
But ...
4
votes
3answers
210 views
Formally prove that $\Theta(\max(f,g)) = \Theta(f+g)$
I am having a hard time proving that $\Theta(\max(f,g)) = \Theta(f+g) $
where
$(f+g)(n) = f(n) + g(n) $
and
$(\max{f,g})(n) = \max(f(n), g(n))$
I know that $\Theta$ is the combination of the ...
0
votes
1answer
62 views
if $a= O(N^2)$, can I also say $a=O(N^4)$?
if $a=O(N^2) $ then according to the big oh definition I didn't see why we can't say $a= O(N^4)$ or $= O(N^8)$
0
votes
1answer
48 views
Asymptotic Notation more specifically, Big-O notation
How the functions in the class $O(d)^d$ and $\epsilon^{1/O(d.4^d)}$ looks like..?
where $\epsilon$<1.
I am really confused with this complicated Big-O notations
Can you please help me out.
5
votes
3answers
138 views
Is there a minimal diverging series?
Is there a function $f:\mathbb{N} \to \mathbb{R}^+$ s.t. its series $\Sigma_{i=0}^\infty f(n)$ diverges but the series for all function in $o(f)$ converge?
1
vote
0answers
22 views
Evaluating a simple sum bound
I'm trying to evaluate and prove a simple statement but It seems really raw/bad solution.
I would like to advise with you if this is the right way because It is really getting more complicated than It ...
2
votes
1answer
66 views
Asymptotic behavior of $\cos(\sqrt{4n+1}x)-\cos(\sqrt{4n+\alpha}x)$
While reading a paper in physics i came across asymptotic behavior of $\cos(\sqrt{4n+1}x)-\cos(\sqrt{4n+\alpha}x)$ and it was written this is equal to $O(n^{-1/4})$ for any real $\alpha$. I tried to ...
1
vote
1answer
34 views
Simplifying Equation - Asymptotic analysis
The textbook I'm using for the course Introduction to Algorithms class has the following statement in it:
The equation of such a line is
$\log (T(N)) = 3 \log N + \log a$
(where a is a ...
3
votes
6answers
183 views
Asymptotic expansion of $ I_n = \int_0^{\pi/4} \tan(x)^n \mathrm dx $
I'm trying to compute the asymptotic expansion of
$$ I_n = \int_0^{\pi/4} \tan(x)^n \mathrm dx $$
Here is what I've done:
Change of variable $$ t= \tan x $$
$$ I_n = \int_0^1 \frac{t^n \mathrm ...
0
votes
1answer
55 views
If not an upper bound, is it a lower bound?
I wanted some help with a bounding question. The question asks that if $f$ is not an upper bound on $g$, is it a lower bound? $f,g: \mathbb{N} \to \mathbb{N} \cup \{\infty\}$.
By definition for an ...
0
votes
1answer
48 views
Proof for asymptotic tight bound when $C=a_k/2$
In an algorithms lecture in school theres a proof for asymptotic tight bound like:
Take $C=a_k/2$ and show that $f(n) \ge \frac{a_k}{2} n^k$ when $n > N$
for some $N$.
$$\begin{align} ...
2
votes
1answer
81 views
How to find asymptotic behaviour?
How do we find asymptotic behavior of Hermite polynomials? I tried to check, but i can only find the final expression but not the method.
1
vote
2answers
80 views
Does little-o notation imply going into infinity?
Let $f(n)=o(g(n))$. By definition there exists $n_0$ so that for all $n>n_0$ it holds that $\varepsilon \cdot g(n) \geq f(n)$ for $\varepsilon>0$ however small.
So, in plain language, starting ...
0
votes
1answer
46 views
for positive functions $f(n)$ and $g(n)$, can $f(n)$ be in $\mathcal{O}(g(n))$ and $\Omega(g(n))$?
For positive functions, is it possible for $f(n)$ to be lower bounded by $g(n)$ if its already being upperbounded by $g(n)$?
If $f(n) = g(n) = n$, then doesn't that mean $g(n)$ is a lower and ...
2
votes
1answer
55 views
Asymptotic expansion of $ u_n = \int_0^1 \ln(1+t^n) \mathrm dt $
I would like to know how I can compute the asymptotic expansion of:
$$ u_n = \int_0^1 \ln(1+t^n) \mathrm dt $$
Using the dominated convergence theorem, we get:
$$ u_n \sim \frac{\pi^2}{12n}$$
How ...
0
votes
5answers
73 views
How to prove that $\log_2(n!) = \Theta(n\log_2[n])$?
My first thought was to use $$\lim_{n\rightarrow\infty}\frac{n!}{n^n} = 0$$so I thought it should be $$\log_2n!=O(n\log_2n=\log_2n^n)$$ but I was told that $$\log_2n!=\Omega(n\log_2n)$$ is also true. ...
0
votes
1answer
44 views
asymptotic expansion, interpretation
I am interested in asymptotic behavior of a function at infinity:
$$
f(r)=\frac{0.04962 e^{-2 r} (r-1.000)}{\left(\left(e^{-2 r}\right)^{2/3}+0.06119\right)^2 r}
$$
Tried ...
1
vote
1answer
101 views
Is the sum always bigger than $n^2$?
Let $s(n)$ an arithmetical function defined as
$$s(n)=(p_1+1)^{e_1} (p_2+1)^{e_2} \cdots (p_m+1)^{e_m}$$
where prime factorization of $n$ is $n=p_1^ {e_1} p_2 ^{e_2} \cdots p_m^{e_m}$.
(For example, ...
1
vote
1answer
75 views
$x \sim y \implies \pi(x) \sim \pi(y) $ and repeated applications of PNT
Let $\sim$ mean if $a \sim b$ then $\lim_{x \to \infty} \frac{a}{b} =1.$
The following is a threshold question. It seems that $x \sim y \implies \pi(x) \sim \pi(y).$
Pf. $\pi(x) \sim \frac{x}{\log ...
2
votes
1answer
43 views
A number-theoretical estimation-inequality
I have some trouble understanding the following number-theoretical estimation:
$$\sum_{k\le \sqrt{n}} (1-k^2/n)^{1+o_n(1)}=n^{1/2+o(1)} \
(n\to\infty),$$ where $o_n(1)$ denotes a $o(1)$ function ...
2
votes
3answers
94 views
$x \sim y \implies \log x \sim \log y$?
Does $x \sim y \implies \ln x \sim \ln y$?
I would have thought not, but the following has almost persuaded me otherwise:
Assume $x \sim y.$ Does this imply that $$\tag{1}I = ...
1
vote
1answer
56 views
Help finding Complexity in Big-O notation
I have found the complexity of an algorithm as the expression below. How can I find the complexity in big O notation for such expression? Or prove that it's bounded by $n^3$ or $n^4$. Can I use triple ...
3
votes
1answer
82 views
Laplace method help
$$\int_{0}^{\infty} \frac{e^{-x \cosh t}}{\sqrt{(\sinh t)}}dt$$
I'm trying to use Laplace's method to find the leading asymptotic behavior as $x$ goes to positive infinity, but I'm having some ...
1
vote
1answer
80 views
Prove $n^\frac{1+2}{\sqrt{\log n}} = O(n \log n)$
Prove that $$n^\frac{1+2}{\sqrt{\log n}} = O(n\ \log n).$$
I want to compute the two growth rates by using L'Hôpital's rule:
$$\lim_{n\to \infty} \frac{f(n)}{g(n)}$$
so I get something like ...
0
votes
1answer
162 views
Dominant term and Big Omega
For the given expression, determine the dominant term and then use the dominant term to classify the algorithm in big-O terms and also in $\Omega$-notation.
$$n^3+n^2\log_2(n)+n^3\log_2(n)$$
So, I ...
0
votes
3answers
80 views
Example of a function according to Big-Oh rules
I am having difficulty understanding the Big-Oh rules. For example , here is a question :
Find example of functions ( which are not negative ) $d(n),f(n),e(n),g(n)$ such that $d(n)$ is $O(f(n))$ and ...
0
votes
1answer
38 views
Asymptotic Complexity Problems with Subtraction
I know that when finding the asymptotic complexity of a given function, you must pay attention to the rate of change in a for loop. For example:
for (i = 1 to n)
{
//some action of constant time ...
2
votes
1answer
252 views
Why is $\pi$ the Limit of the Absolute Value of the Prime $\zeta$ Function?
Motivation:
I was looking at the approximation of the truncated Prime $\zeta$ function
$$
P_x(s)=\sum_{p\leq x}p^{-s}= \mathrm{li}(x^{1-s}) + O \left(\cdot \right)
$$
(to be found here with or ...
0
votes
1answer
740 views
Asymptotic functions
Someone can help me to identify a function $f$ and a functon $g$ which statisfy the conditions specified below:
$f(n) = \operatorname{O}(g²(n))$
$f(n) = \Omega(f(n)g(n))$
$f(n) = \Theta(g(n)) ...
3
votes
2answers
66 views
Asymptotic rate of growth of a sum
Consider $$\Phi_0(x) = \sum_{i=0}^{\infty} (1-x)^i,$$ where $x \in (0,1)$. As $x \rightarrow 0$, $\Phi_0(x)$ blows up as $\Theta(1/x)$. Similarly, consider $$ \Phi_1(x) = \sum_{i=0}^{\infty} i ...
1
vote
2answers
57 views
Asymptotic Expansion of a Multiscale Partial Differential Equation
I'm trying to understand how to solve $$-\nabla\cdot(K(\frac{x}{\epsilon})\nabla u(x,\frac{x}{\epsilon})=f \text{ in } \Omega$$ $$u(x,\frac{x}{\epsilon})=u_D \text{ in } \partial \Omega$$
where ...
5
votes
0answers
97 views
Hints/Help studying an Abel Differential Equation
I want to know more than qualitative information about the Abel differential equation
$\frac{dy}{dx}+y^3+x=0$. $\qquad ... \;(1)$
Since I don´t know how to solve this and as far as could see, this ...
2
votes
1answer
62 views
How to asymptotically estimate a lower bound of this function?
The function is given as
$$f(x)\geq \sum_{i=1}^{[x/2]}f(i)+1$$
The boundary condition is $f(0)=0$.
What I can get is this function grows faster than any polynomial function, and grows slower than ...
3
votes
4answers
121 views
Studying $ u_n = \int_0^1 (\arctan x)^n \mathrm dx$
I would like to find an equivalent of:
$$ u_n = \int_0^1 (\arctan x)^n \mathrm dx$$
which might be: $$ u_n \sim \frac{\pi}{2n} \left(\frac{\pi}{4} \right)^n$$
$$ 0\le u_n\le \left( \frac{\pi}{4} ...
1
vote
1answer
83 views
Big O and Big Omega
For a homework problem, we've been asked to prove the following:
$$6n^2+20n \in O(n^3)$$
$$6n^2+20n \not \in \Omega(n^3)$$
Since BigO is defined as $g(n) \leq c \cdot f(n)$ for a function $f(n)$, ...
5
votes
0answers
126 views
An integration to first order
I am having some trouble evaluating an integral -- involving taking an approximation. It would be great if someone could help me.
I wish to evaluate
$$\int_0^\pi {\cos\theta\cos \left[\omega ...
0
votes
1answer
35 views
Asymptotic dominance for sum of roots.
I'm trying to solve one of the tasks in the Algorithm Design Manual book from Steven Skiena.
The goal is to place the functions into increasing asymptotic order.
$f_1(n)=\sum_{i=1}^n\sqrt{i}$,
...
