Tagged Questions

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
28 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
16 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 ...
0
votes
1answer
14 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
17 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 ...
1
vote
0answers
26 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
10 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 ...
0
votes
1answer
25 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
1answer
19 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 ...
2
votes
0answers
37 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. ...
0
votes
1answer
26 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$ ...
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...
-1
votes
1answer
24 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
0answers
21 views

Disproving a relation between function and derivative concerning Big-O-Notation

The question is to disprove the following: Be $f$ a continuously differentiable function that maps from $\mathbb{R}\rightarrow\mathbb{R}$ and $f(x) =\mathcal{O}(x^2) $ for $x\rightarrow0$, then it ...
0
votes
0answers
32 views

Two estimates of $\sum \log p_2(i)$ using PNT correct?

Let $p_2(i)$ be the i$^{th}$ product of two primes (possibly repeated). Are these estimates correct? $\sum_{i=1}^{n} \log p_2(i) \sim n \log n.\hspace{5mm}(*)$ ...
3
votes
2answers
39 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?
1
vote
0answers
39 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)$ ...
0
votes
0answers
14 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
2answers
65 views
+50

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 ...
1
vote
2answers
49 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 ...
2
votes
3answers
45 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
1answer
34 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
34 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
35 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 ...
4
votes
1answer
100 views
+50

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
0answers
24 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.
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 + ...
0
votes
1answer
29 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$.
0
votes
1answer
27 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
2answers
36 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 ...
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 ...
0
votes
2answers
40 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}} ...
1
vote
1answer
35 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$ ...
0
votes
1answer
22 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 ...
1
vote
1answer
90 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
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}\\ ...
2
votes
0answers
49 views

Finding the critical values of a response curve

I have the motion of a forced spring: $$x'' + \kappa x' + x - x^3 = \varGamma \cos(\omega t) \ \ \cdots \ \ (1)$$ and I am investigating the stability of its solutions with forcing period $T = ...
0
votes
1answer
12 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 ...
0
votes
1answer
32 views

Meaning of the $\{1 + o(1)\}$

Being a software developer, I have the basic understanding of big-O and small-o notation. But currently I've faced set of mathematical problems, where they operate with asymptotics on much more ...
0
votes
1answer
17 views

Recurence Problem. - Solve either by substitution or Expansion

Function T(n) is defined by the following recurrence relation: $$ T(n)=2T(\lfloor\sqrt{ n}\rfloor)+\log(n) $$ $$ T(0)=1 $$ How would I Solve by substitution and/or Expansion? Note: ...
1
vote
2answers
44 views

Estimating the behavior for large $n$

I want to find how these coefficients increase/decrease as $n$ increases: $$ C_n = \frac{1}{n!} \left[(n+\alpha)^{n-\alpha-\frac{1}{2}}\right]$$ with $\alpha=\frac{1}{br-1}$ and $0\leq b,r \leq 1$. ...
0
votes
1answer
21 views

$g(f(n))\in o(g(n)/n)$ for any $f(n)\in o(n)$

Let $f:\mathbb{N}\rightarrow\mathbb{R}$ be a function such that $f(n)\in o(n)$. Is it always possible to find a function $g:\mathbb{N}\rightarrow\mathbb{R}$ such that $g(f(n))\in o(g(n)/n)$? I'm ...
1
vote
1answer
13 views

$g(n)\in\omega(n^r)$ but $g(f(n))\in o(n^{r-1})$

Let $f:\mathbb{N}\rightarrow\mathbb{R}$ be a function such that $f(n)\in o(n)$. Is it always possible to find a function $g:\mathbb{N}\rightarrow\mathbb{R}$ and a constant $r>1$ such that ...
0
votes
1answer
23 views

Big-Oh Notation and Solving for f(x)

Taking Discrete Mathematics and completely lost when it comes to Big-Oh Notation. While I know it's used to profile code I can't figure out how to solve the following problem: Find the least integer ...
11
votes
4answers
136 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
3answers
36 views

O-Notation: How to put the function in order.

I am new here, so I am sorry for any mistake that I'll probably make. I have an exercise to solve, but I didn't really understand how this really works. I am given the functions $2^n$, $n^{0.01}$, ...
9
votes
2answers
148 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}}.$$ ...
0
votes
0answers
17 views

asymptotic esimation of a complex integral

I am searching for a general method to evaluate asymptotically this kind of integral $\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}f(q,\omega)\exp[-\mathrm{i}kr]\exp[-\mathrm{i}\omega ...