Questions involving asymptotic analysis, including growth of functions, Big-O notation, Big-Omega and Big-Theta notations.
0
votes
1answer
43 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, ...
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 ...
1
vote
1answer
74 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
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 ...
0
votes
1answer
85 views
Big Theta equivalence classes and proofs
I have a series of equation and I need to find which are in the same big theta equivalence class and order them. I am super confused by big theta. The equations are:
$\ln(2x)$
$\ln(x)$
$x^2+2x$
...
1
vote
1answer
79 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
160 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 ...
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 ...
2
votes
1answer
59 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 ...
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)$, ...
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} ...
4
votes
0answers
95 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 ...
5
votes
0answers
125 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 ...
4
votes
0answers
62 views
Dominated convergence on $e^{-n^2 t} t^{s/2-1}$
I am trying to apply the Dominated Convergence Theorem to show that
$$\sum_{n\ge 1} \int_0^1 e^{-n^2 t} t^{s/2-1}dt= \int_0^1 \sum_{n\ge 1}e^{-n^2 t} t^{s/2-1}dt$$ as soon as $s>1$.
I've ...
11
votes
1answer
146 views
If $\lambda_n \sim \mu_n$, is it true that $\sum \exp(-\lambda_n x) \sim \sum \exp(-\mu_n x)$ as $x \to 0$?
If $\lambda_n,\mu_n \in \mathbb{R}$, $\lambda_n \sim \mu_n$ as $n \to +\infty$, and $\mu_n \to +\infty$ as $n \to +\infty$, is it true that
$$
\sum_{n=1}^{\infty} \exp(-\lambda_n x) \sim ...
0
votes
1answer
33 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}$,
...
1
vote
1answer
48 views
Big 0h question how are they similar?
How is an algorithm with complexity $O(n \log n)$ also in $O(n^2)$? I'm not sure exactly what its saying here, I feel it may be something to do with the fact that big-oh is saying less than or equal ...
1
vote
1answer
74 views
asymptotic behavior of the real part of the Riemann zeta function for $0<\sigma<1$
consider the zeta function $\zeta(\sigma+it)$ for $\sigma>1$ :
$$\zeta(\sigma+it)=\sum_{n=1}^{\infty}\frac{1}{n^{\sigma+it}}$$
And:
$$\zeta(\sigma-it)=\sum_{n=1}^{\infty}\frac{1}{n^{\sigma-it}}$$
...
10
votes
2answers
185 views
Laplace's method
I'm still having a little trouble applying Laplace's method to find the leading asymptotic behavior of an integral. Could someone help me understand this? How about with an example, like:
...
5
votes
3answers
184 views
“$O$” notation in Stirling approximation
In the Stirling approximation the formula as typically used in applications is
$$\ln n! = n\ln n - n +O(\ln(n))$$
I'm confused about the last term "$O$" . What does it mean actually, and when do we ...
4
votes
2answers
264 views
Asymptotics of system of linear equations
I have a system of linear equations as follows.
$$M(p) = 1+\frac{n-p-1}{n}M(n-1) + \frac{2}{n} N(p-1) + \frac{p-1}{n}M(p-1)$$
$$N(p) = 1+\frac{n-p-1}{n}M(n-1) + \frac{p}{n}N(p-1)$$
$$M(1) = ...
7
votes
3answers
147 views
Asymptotic expansion of a series
I am interested in the asymptotics, as $x$ tends to $0$, of
$$f(x) = \sum_{n=1}^\infty \frac{1}{n}\frac{1}{(e^{nx}-1)^2}$$
This function is well defined for every $x > 0$ (for example, use ...
4
votes
1answer
61 views
Asymptotic value in math.
What does the term $o(k^2)$ in $f(k)=k^2/2+o(k^2)$ mean ?
I have used the asymptotic notation only in context of algorithmic complexity.
With an analogy that, I am guessing it says $f(k)$ returns ...
7
votes
3answers
248 views
How to calculate $\sum \limits_{x=0}^{n} \frac{n!}{(n-x)!\,n^x}\left(1-\frac{x(x-1)}{n(n-1)}\right)$
What are the asymptotics of the following sum as $n$ goes to infinity?
$$
S =\sum\limits_{x=0}^{n} \frac{n!}{(n-x)!\,n^x}\left(1-\frac{x(x-1)}{n(n-1)}\right)
$$
The sum comes from Probability of ...
2
votes
1answer
45 views
Series expansion and approximate solution
I have the following equation: $a(x)k-b(x)=0\Rightarrow k=\dfrac{b(x)}{a(x)}$. I find approximate solutions around $x=0$ by two ways:
(1) I expand the equation as ...
3
votes
3answers
98 views
Result of Bernoulli trials being twice the expectancy?
Given a probability $0 < p < 0.5$ for success per trial with $n$ Bernoulli trials, what are the odds for having succeeded in at least $2np$ experiments?
0
votes
1answer
58 views
What is the vertical asymptote of $y=2x-\arccos(\frac{1}{x})$?
I have to find the vertical asymptote of $y=2x-\arccos(\frac{1}{x})$. So I have to find the limit of the function when $x$ approaches zero. In my textbook it says that the vertical asymptote does not ...
3
votes
0answers
88 views
Saddle point and stationary point approximation of the Airy equation
Happy New Year to you all.
Let $$\tag 1 J(N)=\int_a^b e^{Nf(x)}dx$$ where $N\in\mathbb R$ and $N>>1$ and $f(x)$ has a global maximum at $x=x_0$ with Taylor expansion $$f(x) \approx ...
2
votes
3answers
50 views
How to find asymptotes of $y=ax+b+\frac{c+\sin x}{x}$
How can we find the asymptotes of $y=ax+b+\frac{c+\sin x}{x}$?
15
votes
2answers
697 views
please solve a 2013 th derivative question?
$ f(x) = 6x^7\sin^2(x^{1000}) e^{x^2} $
Find $ f^{(2013)}(0) $
A math forum friend suggest me to use big O symbol, however have no idea what that is, so how does that helping?
0
votes
1answer
88 views
Is this why this summation is equivalent to this Theta notation?
So I'm not sure if I misunderstood the lesson or not.
$$T(n) =\sum_{j=2}^{n}\Theta(j) = \Theta(n^2) $$
Are these equivalent because:
$$ \sum_{j=2}^{n}\Theta(j) = \frac{n(n-1)}2 - \frac{1(1 - 1)}{2} = ...
1
vote
1answer
88 views
Show that $(n + a)^{b}$ = $\Theta(n^{b})$
In the book I'm following I got the following solution:
To show that $(n + a)^b = \Theta(n^b)$, we want to find constants $c_1, c_2, n_0 > 0$ such that $$0 \leq c_1 n^b \leq (n + a)^b \leq c_2 ...
0
votes
1answer
400 views
How to prove that $\max(f(n), g(n)) = \Theta(f(n) + g(n))$?
Using the basic definition of theta notation prove that $\max(f(n), g(n)) = \Theta(f(n) + g(n))$
I came across two answer to this question on this website but the answers weren't clear to me. ...
2
votes
2answers
69 views
How to show $n! = \omega\big((\frac{n}{3})^{n+e}\big)$?
I'm learning some mathematics by myself and get stuck. The problem is to show that
$n! = \omega\big((\frac{n}{3})^{n+e}\big)$, $\omega$ is the asymptotic notation.
It's from the Problem Set 7 of MIT ...
2
votes
1answer
83 views
Does $\Theta(m \log n)$ and $0 < m < n^2$ imply $\Theta(n^2 \log n)$?
If we have an algorithm with complexity $\Theta(m + n^2)$ and we know that $0 < m < n^2$ then its complexity becomes $\Theta(n^2)$. But if we had an algorithm with complexity $\Theta(m\log{n})$ ...
4
votes
3answers
139 views
Number of representable as sum of 2 squares
How to find asymptotically (or some reasonable bound, at least $ o(n) $) number of numbers, representable as a sum of squares of 2 numbers? (in case of bound I am interested in both: lower and upper ...
4
votes
1answer
59 views
Asymptotics with prime of form 4k+3
I wonder if there is some asymptotics for such sum: $ \sum_{p=2}^{n} \frac{1}{p}$, where the sum is taken over all primes of form $ 4k+3 $?
It's well-known that $ \sum_{p=2}^{n} \frac{1}{p}$, where ...
2
votes
2answers
89 views
$f(x)=\int_{0}^{1}e^{ixz^2}dz$ as $x\rightarrow +\infty$.
Find the asymptotic behaviour as $f(x)=\int_{0}^{1}e^{ixz^2}dz$ as $x\rightarrow +\infty$.
Could anyone show me how to do this with either the method of stationary phase or integration by parts?
...
1
vote
1answer
55 views
Matched Asymptotic Expansion - Stretching Transofrmation
I'm having problems getting my head around a stretching transformation in the method of matched asymptotic expansions. I'm reading Introduction to Perturbation Methods (by Holmes) and he discusses the ...
1
vote
0answers
64 views
Asymptotic analysis for multiple variables?
How is asymptotic analysis (big o, little o, big theta, big theta etc.) defined for functions with multiple variables?
I know that the Wikipedia article has a section on it, but it uses a lot of ...
1
vote
0answers
69 views
“Balancing” two infinities
Given these two computational complexities of 2 algorithms (factoring):
$\exp(O(\sqrt{\log n \log \log n}))$
$O(\sqrt{\exp n} / \log{ \sqrt{ \exp n} })$
where I imagine the first one goes to ...
3
votes
2answers
24 views
Simple question about asymptotics of a ratio
What is the largest exponent $\alpha$ such that the ratio between $ n^{\alpha}$ and $ (\sqrt{n} / \log{ \sqrt n}) $ still remains asymptotically bounded (can assume $n$ positive integer) ?
0
votes
1answer
117 views
If $f(n) = \Theta (g(n))$, why does $g(n) = \Omega (f(n))$?
Why is this the case? I understand that if $f(n) = \Theta (g(n))$ then $c_1g(n)<f(n)<c_2g(n)$, but why does this show that $g(n)$ is bounded below by $f(n)$? I would think that it would be ...
2
votes
0answers
47 views
asymptotics of $ J_{iu} (ia)$ for a Bessel function
Let $J_{iu}(ia)$ be the Bessel function of imaginary order. ($a$ is a real number (positive or negative) and $u$ is also real.)
In the limit $u \to \infty $ how does the function $J_{iu} (ia)$ ...
