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
0answers
26 views

Calculate the leading-order asymptotic behaviour (Laplace's Method) [duplicate]

thanks in advance! Calculate the leading-order asymptotic behaviour of the integral $$I(x) = \int_{0}^{2\pi} (1+t^2) e^{x \cos t} dt \mbox{ as } x \mbox { tends to infinity}$$ So far I know there ...
0
votes
2answers
40 views

Show that $3n^2 - n+4$ is $O(n^2)$

From the definition of big oh: We say that "$f(n)$ is big oh $g(n)$" if there exists an integer $n_0$ and a constant $c>0$ such that for all integers $n\geq n_0$, $f(n)\leq cg(n)$. Substituting ...
0
votes
2answers
15 views

Determine the asymptotic behavior of $f(n)$ in relation to $g(n)$

$f(n)=n^\sqrt{n}, g(n)=2^n$ $f(n)=10^{\log\log n}, g(n)=\log n$ Note: $\log$ is in base 2. For section #1, I tried to evaluate the limit $\lim_{n\to\infty} \frac{2^n}{n^\sqrt{n}}$ but got stuck ...
1
vote
0answers
25 views

How to prove that a function f(x) is O(g(x)), using the definition (finding C and k)

We say that $f(x)$ is $O(g(x))$ if $$(∃C ∈ \mathbb(R)❘)(∃k ∈ \mathbb(R)❘)(∀x ∈ \mathbb(R)❘)$$ $$(x ≥ k → |f(x)| ≤ C · |g(x)|)$$ In English: We can find $C$ and $k$ so that, once we get past the “small ...
0
votes
0answers
28 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 ...
1
vote
1answer
40 views

Asymptotic solution to a differential equation near zero

I am trying to get the both the asymptotic solutions of the equation $y''(x)=\sqrt{x} \cdot y(x)$ as $x\rightarrow 0$. But when I put $y(x)=\exp(S(x))$ since $x=0$ is an irregular singular point, no ...
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{ }?$$ ...
2
votes
1answer
39 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\\ ...
1
vote
2answers
76 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 ...
0
votes
1answer
30 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
29 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
14 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
1answer
90 views

Proof of simple relation involving near primes?

Motivation (can skip!). (*) $\sum\log n \approx n\log n-n,$ and $$\sum\log n = \sum_{p_1\leq n} \log p_1+\sum_{p_2\leq n} \log p_2+...+\sum_{p_m\leq n} \log p_m$$ in which $p_k$ are numbers comprised ...
0
votes
0answers
25 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
18 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?
3
votes
2answers
39 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
19 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
19 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
34 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
33 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
16 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
28 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 ...
3
votes
1answer
26 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
54 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
38 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
56 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
36 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
44 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 ...
4
votes
2answers
76 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
1answer
59 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)$ ...
2
votes
1answer
20 views

Recursion and Time Complexity Concept

The question prompt is as follows: Consider the function $f(n)$ defined as: $$f(n) = \begin{cases}n(n-1)f(n-2) & n > 1\\1 & n=0,\; n=1\end{cases}$$ How may be $g(n)$ be defined ...
0
votes
0answers
21 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
73 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 ...
1
vote
2answers
55 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
67 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
55 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
31 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
37 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
40 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
113 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
0answers
29 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
22 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
32 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
44 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
40 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
36 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
7 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
48 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
49 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
30 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 ...