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

learn more… | top users | synonyms (1)

0
votes
0answers
27 views

Am I to place my trust in Wolfram on this matter? [Oblique asymptotes on a function]

So I used Wolfram to find oblique asymptotes for the following function $f(x) = 2x + 3 - \frac{1}{\ln x}$ The vertical asymptote, which Wolfram finds as well, is $x=1$. However, my method for finding ...
2
votes
3answers
429 views

big O notation with asymptotically nonnegative increasing functions

Let $f(n)$ and $g(n)$ be asymptotically nonnegative increasing functions. Show: $f(n) · g(n) = O((\max\{f(n), g(n)\})^2)$, using the definition of big-oh. I can't quite figure this out, can ...
1
vote
1answer
85 views

Find asymptotics in a given form $n=(e+o(1))^{f(s)}$

Let $p\to\infty$, $s={\binom {p^4} p}$ and $n={\binom {p^4}{p^2}}$. Find a function $f(s)$ in the following form $$\large n=(e+o(1))^{f(s)}$$ I've tried to use the followinf asymptotics for ...
0
votes
1answer
39 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
1answer
58 views

$\frac{a_n - a_{n+1}}{a_n} \approx \frac{1}{n}$? (part of 2010 Putnam exam)

Given a non-negative sequence $a_n$, strictly decreasing and tending to zero, can we show that (for large $n$) $$ \frac{a_n - a_{n+1}}{a_n} \approx \frac{a_n}{na_n} = \frac{1}{n} \text{ }?$$ ...
1
vote
2answers
66 views

Solving $T(n)= 2T(n/2) + \sqrt{n}$ without master theorem (algebraically & recurrence tree)

$$T(n)= 2T(n/2) + \sqrt{n}$$ This recurrence was in a stackoverflow question, and I want to solve it without relying on the master method. The solution was given, but wolframAlpha gives a slightly ...
2
votes
1answer
38 views

Finding an upperbound on $f(n)$

I am stumped trying to prove that there exists a real number $c$, such that $f(n)\leq cn^4$ for most natural numbers $n$. $$f(n) = \left\{ \begin{array}{ll} 10, &n=10\\ ...
0
votes
1answer
29 views

Prove that $\log^\alpha n = o( a^n )$

Please, how to prove: $\forall c \in \mathbb R_+$ $\exists n_0 \in \mathbb N_+$ $\forall n \ge n_0 :$ $log^\alpha n < c \cdot a^n$ for $ \\a>1$, $\alpha \in \mathbb R$ ? Thanks
0
votes
1answer
27 views

Solving $T(n) = 8T(\lfloor \frac{n}{2}\rfloor) + 1$ using Akra-Bazzi

I was trying to apply Akra-bazzi to solve $T(n) = 8T(\lfloor \frac{n}{2}\rfloor) + 1$ but I was having some issues. I was told that the correct way to solve it to express the floor in the form (for ...
0
votes
0answers
12 views

Asymptotic power series of $F(x)= \int_{0}^{T} f(t) e^{-xt}dt $

Let $f \in C^{\infty}$ and $T>0$. I am asked to find an asymptotic power series of the funtion: $$ F: \mathbb{R}_{+} \rightarrow \mathbb{R}, \quad F(x)= \int_{0}^{T} f(t) e^{-xt}dt$$ as $x ...
0
votes
0answers
24 views

Binomial series using gamma function

I am trying to find a formula of this online but am having a lot of trouble. In my textbook (Bender and Orszag), they make the following transformation for small $t$: ...
0
votes
1answer
17 views

Limit of multivariate polynomial with large arguments

If I have a polynomial $f(x,y)=x^4+y^4-4xy$, how would I go about showing that as the standard norm of $(x,y)$ goes to infinity, $f(x,y)$ goes to infinity?
1
vote
1answer
58 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
34 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
32 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 ...
11
votes
4answers
189 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
31 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
15 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
27 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
53 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
36 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$ ...
3
votes
2answers
172 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
35 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
55 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
87 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
73 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
319 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
20 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 ...
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
48 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
36 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
37 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
91 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
37 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
108 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
159 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
828 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
31 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 ...