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

learn more… | top users | synonyms (1)

1
vote
1answer
56 views

Is this expression for $p_2(n)$, the nth composite of two primes, correct?

The PNT gives an expression for the n$^{th}$ prime: $n\log n.$ My question is whether $$p_2(n) \sim \frac{n\log n}{\log\log n} $$ is the correct analogous form for 2-primes $p_2(n)$ ...
3
votes
2answers
37 views

What can we say about the rate of growth of a function growing faster than all polynomials?

Suppose $f: \mathbb{R} \rightarrow \mathbb{R}$ satisfies the following: $$ \forall k \in \mathbb{N} \hspace{5pt} \lim_{t \rightarrow \infty} \frac{t^k}{f(t)} = 0.$$ Can we deduce a stronger growth ...
0
votes
1answer
18 views

Simple Question: division of sums

I am a little bit confused about the following simple task. Given some functions $f(x), g(x), h(x), l(x), m(x)$. We know that $\frac{f(x)}{g(x)}= m(x)$. We further know that $h(x), l(x)$ are ...
2
votes
0answers
32 views

Asymptoticity of a definite integral

friends! I read on a book that, for $\alpha>1$, "being $g$ continuous in 0 [really $g$ is continuous in $[0,1]$, if it were useful to know] and approaching the extremes of the integral 0 for $n\to ...
0
votes
1answer
17 views

How to deal with such inequalities?

I have that $$ Y \geq n e^{- 1- t \log t + o(1)}$$ and $$Y \leq n e^{\log n +t - t \log t}.$$ Now I would like to find values $t_0(n)$ and $t_1(n)$ such that $$Y \rightarrow 0 \text{ for all } t ...
0
votes
0answers
30 views

Asymptotic expansion at infinity of integral function

Given $q\in(0,1)$ find $z$ such that $$ F(z)\equiv\int_{-\infty}^{z}\frac{e^{-\frac{y^2}{2 \sigma _{22}^2}} \text{erfc}\left(\frac{\rho \sigma _{11} y-\sigma _{22} V}{\sqrt{2-2 \rho ^2} \sigma ...
0
votes
1answer
403 views

How does adding big O notations works

can someone please explain how adding big O works. i.e. $O(n^3)+O(n) = O(n^3)$ why does the answer turn out this way? is it because $O(n^3)$ dominates the whole expression thus the answer is still ...
11
votes
4answers
168 views

Infinite Sum of Sines With Increasing Period

A while ago, I was thinking about the Weierstrass function, which is a sum of sines with increasing frequencies in such a way that the curve is a fractal. However, I wondered what would happen if one ...
1
vote
0answers
29 views

Asymptotic expansion of $(\text{log}(1+x))^2$

How can I find asymptotic expansion of the function $(\text{log}(1+z))^2$ with respect to the asymptotic scale $\{z^{-m}, z^{-n}\text{log}(z), z^{-p}\text{log}^2(z), m,n,p=0,1,2,...\}$ while ...
0
votes
1answer
13 views

Prove asymptotic bound by the substitution method

I need to prove that $T(n) = 4T(n/2) + n^2lgn = \mathcal{O}(n^2lg^2n)$ by using the substitution method. Unfortunately, I'm not able to identify the error in my train of thought. For the problem at ...
2
votes
2answers
72 views

Calculate limit $\lim_{n\rightarrow\infty}\dfrac{(4n-100)^{4n-100}n^n}{(3n)^{3n}(2n)^{2n}}?$

The limit $$\lim_{n\rightarrow\infty}\dfrac{(4n)^{4n}n^n}{(3n)^{3n}(2n)^{2n}}$$ can be calculated as ...
0
votes
1answer
26 views

asymptotic expansion of this integral

How to get the asymptotic expansion for this integral $\int_{0}^{1}\exp(-x/t)dt $ in the limit $x\rightarrow 0$ ? I took $x/t=u$ and did integration by parts (IP) but if I keep doing IP, I get a ...
2
votes
0answers
51 views

Difficulty with Asymptotic Expansion of $\int_{0}^{1}\sqrt{t}e^{ixt}dt$

In the book Advanced Mathematical Methods for Scientists and Engineers by Bender and Orszag (question 6.50) we are asked to compute the asymptotic expansion of $\int_{0}^{1}\sqrt{t}e^{ixt}dt$ fully. ...
3
votes
1answer
23 views

Is the Pattern in the Number of Digits in the Bernoulli Numbers Showing Something Significant

For the first couple of powers of $10$, the number of digits in these show a certain pattern, is this a coincidence or is their a reasonable explanation. Specifically if we look at $$ \lfloor ...
0
votes
1answer
34 views

laplace method on this integral

How to get the leading asymptotic expansion for this integral $\int_{0}^{\pi/2}\sqrt{\sin(t)}\exp(-x\sin^4(t))dt $ in the limit $x\rightarrow\infty$ ? Because the maximum of the exponent is at $t=0$ ...
8
votes
2answers
167 views

Algorithm for adding n 1-bit numbers

suppose adding two numbers, (that first number has a bits and second number has b bits) can be done in ...
-1
votes
1answer
28 views

Asymptotic Expression for the Twin Prime Counting Function

A variation on a previous question I asked, which has garnered no responses. I'll attempt to be more lucid: Let $\pi_2(x)$ be the twin prime counting function and $\pi(x)$ be the prime counting ...
0
votes
1answer
53 views

Asymptotic expansion of $\sin\left(\pi + \exp(-1/\epsilon)\right)$

I need to find the two term asymptotic expansion of $\sin\left(\pi + \exp(-1/\epsilon)\right)$ as $\epsilon$ tends to zero, but the exponential term is confusing me...
3
votes
1answer
85 views

How to find asymptotics of this sum

Is there any way to find $f(n)$ in this term: $$\sum_{k=2}^n \frac1{\ln \ln(k!^{k!})} \sim f(n)?$$ The tilde symbol means that $$\lim_{n\to∞} \frac{f(n)}{\sum_{k=2}^n \frac1{\ln \ln(k!^{k!})}} = 1$$ ...
4
votes
2answers
61 views

Asymptotic expansion for Fresnel Integrals

If you take the fresnel integrals to be $$S(x) = \int_{0}^{x}\sin \left(\frac { \pi \cdot t^2}{2} \right) dt$$ How do you find the asymptotic expansion? I know it begins with a $1/2$ but how?
8
votes
3answers
318 views

How to evaluate $\sum\limits_{k=0}^{n} \sqrt{\binom{n}{k}} $

Can we find $$ \sum_{k=0}^{n} \sqrt{\binom{n}{k}} \quad$$ This problem asked me my friend about a year ago, but I didn't know how to attack problem. Now, I am interesting in solution. Any suggestion? ...
0
votes
0answers
17 views

Exponential Averaging Asymptotic Inequality

Let $\lambda_1(t)$ and $\lambda_2(t)$ be nonnegative integrable functions on $[0,\infty)$. Consider the averaging function of $\lambda_1$ $$k(t) = \frac{\int_0^t \lambda_1 e^{-\int_0^s ...
2
votes
3answers
47 views

Asymptotic behavior of $\sum\limits_{k=1}^n \frac{1}{k^{\alpha}}$ for $\alpha > \frac{1}{2}$

As the title states, I'm interested in the asymptotic behavior of $$\sum\limits_{k=1}^n \frac{1}{k^{\alpha}} , \alpha > \frac{1}{2}$$ for $n \to \infty $. Any hints/ideas?
1
vote
2answers
53 views

Does $\sum\limits_{k=1}^n a_k^2$ imply $\sum\limits_{l=1}^k a_k \in o(\sqrt{n})$?

I'm trying to determine some limits and it makes me wonder if my intuition about asymptotics is just wrong: Our calculus professor used to say that $\sum\limits_{n=1}^{\infty} \frac{1}{n}$ is ...
4
votes
1answer
112 views

If $f(x) = \sum \limits_{n=0}^{\infty} \frac{x^n}{2^{n(n-1)/2} n!}$ then $f^{-1}(f(x)-f(x-1))-\frac{x}{2}$ is bounded

For every $x>0$, let $$f(x) = \sum \limits_{n=0}^{\infty} \dfrac{x^n}{2^{n(n-1)/2} n!}.$$ Let $f^{-1}$ be the functional inverse of $f$. How to show there exists a positive real constant $C$ such ...
1
vote
1answer
44 views

Landau Big O, Little o notation, complex example

I stumbled upon a set cardinality asymptotics: $$O(n^{o(1)}),$$ I have a problem interpreting it. Can somebody give me a hint how to look at it?
1
vote
0answers
30 views

What does “combining the solutions in O(n) time” mean?

Algorithm $X$ proceeds by recursively solving $5$ subproblems of one-half the size, then combining the solutions in $O(n\log n)$ time. Algorithm $Y$ makes $9$ recursively calls on ...
0
votes
1answer
35 views

How to quickly determine running time of such recurrence relations?

$$T(n)=5T(\frac{n}{2})+n\log n$$ $$T(n)=9T(\frac{n}{3})+n^2$$ $$T(n)=2T(\frac{2n}{3})+n^{1.5}$$ What are the running times of each $T(n)$? Each one looks like the form of the Master Theorem, but only ...
0
votes
2answers
36 views

Solve the recurrence $T(n)=3T(n/3)+\log n$, $T(1)=1$

So $T(n)=3T(n/3)+\log n$ and $T(1)=1$. I tried to solve this by expanding it out to see a pattern, but I don't really see the pattern: $T(n/3) = 3T(n/9)+\log (n/3)$ $T(n) = 3[3T(n/9)+\log ...
1
vote
2answers
88 views

Growth of $\sum_{x=1}^{n-1} \left\lceil n-\sqrt{n^{2}-x^{2} } \right\rceil$

I'm interested in the growth of $$f(n):=\sum_{x=1}^{n-1} \left\lceil n-\sqrt{n^{2}-x^{2} } \right\rceil \quad \text{for}\quad n\rightarrow\infty $$ Progress (From comments) I've got ...
0
votes
1answer
35 views

Partial sums of powers of the divisor function

It is easy to establish that $$\sum_{n\le x}\tau(n) \sim n\log n$$ How would one find good bounds on $$\sum_{n\le x} \tau(n)^k $$ for some $k > 0$
1
vote
0answers
28 views

Help with understanding how to sketch a graph of y=1/f(x) and y = xf(x)

I'm having problems trying to figure out how to sketch a graph for these 2 questions. Could someone provide me a step by step guide on how to do this? Thanks in advance.
1
vote
2answers
87 views

How to solve the recurrence relation for tight asymptotic bound without using master theorem?

I have the following recurrence in my problem: $$T(n)= 4T(n/2)+n.$$ I have solved it by substitution by assuming the upper bound $O(n^3)$ but in solving it for $O(n^2)$ i am having some problems.I ...
0
votes
2answers
21 views

Is there a mistake in this page on asymptotic expansions?

I think there is an error in section 4.3 of this page - http://aofa.cs.princeton.edu/40asymptotic/ The author says that by taking $x = -\frac{1}{N}$ in the geometric series $\frac{1}{1-x} = 1 + x + ...
9
votes
2answers
156 views

An asymptotic expression of sum of powers of binomial coefficients.

Let $k$ be a fixed positive number and $n$ an integer increasing to infinity. Then $$\sum_{\nu =0}^n \binom{n}{\nu}^k \sim \frac{2^{kn}}{\sqrt{k}} \left( \frac{2}{\pi n} \right)^{\frac{k-1}{2}}.$$ ...
1
vote
3answers
789 views

Is 'every exponential grows faster than every polynomial?' always true?

My algorithm textbook has a theorem that says 'For every $r > 1$ and every $d > 0$, we have $n^d = O(r^n)$.' However, it does not provide proof. Of course I know exponential grows faster ...
0
votes
1answer
31 views

Is master theorem applicable to the recurrence relation $T(n) = T(n/2)$?

Is master theorem applicable to the recurrence relation $T(n) = T(n/2)$? I do not think it applies because there no $n$ term and there is no $n^k$ for a $k$ which would equal $0$.
1
vote
2answers
37 views

$\lim\limits_{t\to\infty}t-x(t)=0\ ?$

Let $\displaystyle\cases{ x'=\frac{t-x}{1+t^2+x^2} & \cr x(1)=1 }$ be the Initial value problem, prove or disprove $\lim\limits_{t\to\infty}t-x(t)=0$ We've already proved that: for $t>1, ...
0
votes
1answer
29 views

Asymptotic equivalence and $\lim_{x\to 0} \frac{\sin x}{x}=1$

I know that for $x\sim0$ $\sin x$ can be approximated by $x$, hence they are 'asymptotic equivalent in the neighborhood of $x=0$'. According to the definition of asymptotic equivalence, two ...
2
votes
1answer
145 views

Does $\Theta(m \log n)$ and $0 < m < n^2$ imply $\Theta(n^2 \log n)$?

From a function in $\Theta(m + n^2)$ and $0 < m < n^2$, We conclude it is in $\Theta(n^2)$. Does a function in $\Theta(m\log n)$ so that $0 < m < n^2$, imply that it is in $\Theta(n^2\log ...
0
votes
1answer
5 views

If some function f is in big O(some function g), do f and g necessarily need to have the same domain and codomain?

Say I have a function, $g:\mathbb{R} \mapsto \mathbb{R}$. Then would the set $O(g)$ be defined (as explicitly as possible) as: $$O(g) = \{ f:\mathbb{R} \mapsto \mathbb{R} \space|\space \exists C \in ...
3
votes
3answers
157 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 = ...
0
votes
2answers
46 views

Simple equivalent of the rest of the series $\sum\limits_n\frac1{n^3}$

Consider the converging series \begin{equation} \sum_{n\geqslant1}{\frac{1}{n^3}} \end{equation} I want to find an equivalent of the rest : \begin{equation} R_n=\sum_{k=n+1}^{\infty}{\frac{1}{k^3}} ...
0
votes
1answer
36 views

Big O notation for complex-valued functions of a real variable

Let $f,g:\mathbb R\to\mathbb C$. Is there a standard notion of $f = O(g)$? If I had to take a stab at a definition, I'd try something like $f = O(g)$ provided there exists $M>0$ and ...
1
vote
1answer
40 views

Applying the master theorem

State the asymptotic runtime found by the master theorem. If the master theorem does not apply state why: 1) $T(n) = $T($n/3)$ 2) $T(n)= $ $5T$($2n/5$) + $n$ 3) $T(n) = 4T(n/2) +15n^3 + 4n^2 +n+4$ ...
1
vote
1answer
91 views

A limit with $((n-1)!)^{1/(n-1)}$ and other roots of factorials

How to prove that the following limit is positive? $$ \lim_{n \to \infty}\left(((n-1)!)^{1/(n-1)}-2\left(\frac{((n-1)!)^3}{(2n-2)!}\right)^{1/(n-1)}\right) >0,$$ where $ n\in \mathbb Z, n>1 ...
0
votes
1answer
24 views

Asymptotic bounds for the solutions of 3d wave equation

Let $u$ solve the 3-d wave equation: $u_{tt}-\Delta u =0$ such that $u=g$ and $u_t=h$ for $t=0$ and where $g$ and $h$ are both assumed to be compactly supported and smooth. I have shown that there ...
0
votes
1answer
17 views

Why does $f(x) \asymp g(x) \implies log(f(x)) = log(g(x)) + O(1)$?

Why does $f(x) \asymp g(x) \implies log(f(x)) = log(g(x)) + O(1)$? Has it got something to do with the fact that \begin{align} f(x) \asymp g(x) \implies \exists c_1,c_2, \text{ such that}\\ ...
0
votes
1answer
13 views

Show that $\frac{1}{e^\gamma \text{log }x + O(1)} = \frac{1}{e^\gamma\text{log }x} + O\left(\frac{1}{(\text{log }x)^2}\right)$

Show that $\frac{1}{e^\gamma \text{log }x + O(1)} = \frac{1}{e^\gamma\text{log }x} + O\left(\frac{1}{(\text{log }x)^2}\right)$ I'm using one of Merten's estimates in a proof, the one that states ...
1
vote
1answer
26 views

Large $t$ asymptotics of $\int_0^{\infty}\exp(-tx)\exp(-\frac{1}{x^2})dx$

How do I find the asymptotic behavior of $$\int_0^{\infty}\exp(-tx)\exp\left(-\frac{1}{x^2}\right)dx$$ as $t\to\infty$? The Laplace method apparently doesn't work since $\exp(-\frac{1}{x^2})$ isn't ...