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)

1
vote
0answers
10 views

Reworking $\sum_{n \leq x} \frac{1}{n^s}$, where $n$ is relatively prime to some fixed $k$

For a fixed integer $k \geq 1$ and real $s>0$ I want to rework the partial sums $$\sum_{\substack{ n \leq x \\ gcd(k,n) = 1 }} \frac{1}{n^s}$$ in such a way that I can find an asymptotic ...
1
vote
0answers
35 views

$\epsilon y''+\sqrt{x}y'+y=0$, show there is no boundary layer at $x=1$ and a boundary layer of $\epsilon^{\frac{2}{3}}$ at $x=0$?

I'm so lost. If I use quadratic formula I obtain that: $$y(x) = ae^{-2\epsilon\sqrt{x}}+be^{-2x\sqrt{x}+2\epsilon\sqrt{x}}$$ with the boundary conditions $y(0)=0$ and $y(1)=1$ but how does this lead ...
1
vote
1answer
28 views

Obtain the leading order uniform approximation of the solution to: $\epsilon y'' +(1+x)^2y'+y=0$?

Obtain the leading order uniform approximation of the solution to: $\epsilon y'' +(1+x)^2y'+y=0, y(0)=0 y(1)=1$ as $\epsilon \rightarrow 0$. I am completely lost. Am i right in doing this? Since ...
0
votes
0answers
17 views

Do we recognize higher degree asymptotes beyond Horizontal and Oblique?

I am reading a textbook, and it talks about doing synthetic division in order to rewrite a function into the quotient $$R(x)=\frac{p(x)}{q(x)}= f(x) + \frac{r(x)}{q(x)}$$ Since $\frac{r(x)}{q(x)}$ ...
1
vote
1answer
30 views

How can I write in Landau notation (or the like) that $2^x/x$ rises almost as fast as $2^x$?

Since $2^x \not\in O(2^x/x)$, we do not have $O(2^x/x)=O(2^x)$. But since $x$ rises linearly and $2^x$ exponentially, $2^x/x$ rises almost as fast as $2^x$. Can I somehow express this in Landau ...
0
votes
1answer
24 views

Strict upper and lower bounds of a sum (Big-Theta)

I am trying to find a function f(k) such that $S_k=\sum_{n=1}^{k^2-1}(\lfloor\sqrt{n}\rfloor)=\Theta(f(k))$. What I have done so far: Ignoring the floor asymptotically we get: ...
3
votes
1answer
44 views

Determining the asymptotics of the Summatory function of an Arithmetic Function

We define the arithmetic function: $\displaystyle f(n) = \max\limits_{p^{\alpha} || n} \alpha$, that is if $\displaystyle n = p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ (prime factorization of $n$) then ...
1
vote
1answer
20 views

Subtraction of functions with BigO

When trying to assess the BigO of two functions that are added together, we take the max of the two. What happens if there is subtraction instead of addiiton? for instance: $$f(n) = bigO(n^3) $$ $$ ...
2
votes
2answers
21 views

Analytic Combinatorics to asymptotically estimate the number of objects of size at most n?

I have read some bits of Flajolet's and Sedgewick's book on Analytic Combinatorics. I am quiet curious as how to asymptotically estimate the number of objects of size at most n. Suppose for example ...
-2
votes
0answers
10 views

asymptotic distribution (Inference statistic) [on hold]

Assume $Pr(A_{j}) = p^{0}_{j}$, $j = 1,...,k$. Obtain the asymptotic distribution of the statistic $f(\hat{p_{1}},...,\hat{p_{n}})$ = $n\sum_{j=1}^{k}p^{0}_{j}(1 -\frac{\hat{p_{j}}}{p^{0}_{j}})^{2}$. ...
1
vote
1answer
25 views

Arrange in increasing order of asymptotic complexity

I have to arrange the above time complexity function in increasing order of asymptotic complexity and indicate if there exist functions that belong to the same order. So, my answer is $[lg(n)]^2$ ...
0
votes
0answers
22 views

Analytic function with inconsistent asymptotic behaviour on rays

Consider an function $f$, defined continuously on the closed upper half plane, and analytic on the upper half plane. Going along any ray from the origin that go strictly up (ie. not along the real ...
0
votes
0answers
19 views

Laplace's Method modifications

I was wondering if there is a "Laplace's Method" to estimate, as $n \to \infty$, integrals of type $$ I_n = \int_0^\infty e^{nh(x)}g(nx) \, dx $$ where $g$ is a smooth function, that converges to a ...
2
votes
0answers
30 views

Asymptotic of a real double serie on $\mathbb{Z}$

I am interested by a real sequence $\{a_n\}_{n\in\mathbb{Z}}$ as $\sum_{n\in\mathbb{N}}\left(\vert a_n\vert + \vert a_{-n}\vert\right)$ converges. I want to find the asymptotic behavior of this ...
0
votes
0answers
9 views

random variables stochastically bound problem

Could you help me about stochastically bound problem for random variable. show that, there exist a sequence of {a_n} of positive real numbers such that X/a_n->0 a.s for any random variable X.
1
vote
1answer
60 views

Why is $(\log n)^3\in O(\sqrt n)$?

Comparing the order of growth of the two functions by taking a limit and using l'hospitals rule, it seems that $\sqrt{n}$ should be O($log^3n$). Here are the steps I took: $$\lim_{n \to ∞} ...
3
votes
2answers
56 views

Can one apply a WKB method to an inhomogeneous first order differential equation in order to find the asymptotic expansion of the solution?

Consider \begin{equation} \varepsilon \frac{dy}{dx} = Q(x)y + R(x) \end{equation} where $\varepsilon$ is a small parameter. Can one apply a WKB method to find an asymptotic expansion for the ...
1
vote
2answers
60 views

Big theta proof [closed]

a) Show that $3x+7$ is $\Theta(x)$. b) Show that $2x^2 +x -7$ is $\Theta(x^2)$ c) Show that $⎣x+.5⎦$ is $\Theta(x)$ d) Show that $\log_{10}(x)$ is $\Theta(\log_2(x))$ My professor gave the ...
1
vote
0answers
10 views

Integral of product of Hermite functions with rescaled weights.

Let $$h_{k}(x)=c_{k}(-1)^k e^{\frac{x^2}{r^2}}\frac{d^k}{dx^k}e^{-\frac{x^2}{r^2}}$$ be the standard Hermite polynomials, rescaled with a given parameter $r>0$. The normalizing constant ...
1
vote
0answers
18 views

Proof that difference equations as asymptotic to their differential analog.

Given a difference equation $a_{n+k}=f(a_n,a_{n+1},\dots,a_{n+k-1})$, we can classify $n=\infty$ as an ordinary, regular singular, or irregular singular point by classifying $x= \infty$ in the ...
0
votes
1answer
34 views

Big O - arithmetic rules

I need to prove the following statement: $O(f(n)g(n))=f(n)O(g(n))$ At first I thought the statement is false but apparently it is true. How can I prove it?
4
votes
1answer
69 views

How to show $\sum_{i=1}^{n-1} \frac{i(n-2)!}{(n-1-i)!n^{i+1}} \sim 1/n$

How can one compute the large $n$ asymptotics of $$\sum_{i=1}^{n-1} \frac{i(n-2)!}{(n-1-i)!n^{i+1}}\;?$$ My guess is that it is $1/n$ but I don't know how to show that.
5
votes
2answers
72 views

How to show that $\sum_{x=1}^\infty \prod_{i=1}^{x-1} (1-i/n) \sim \sqrt{\frac{\pi n}{2}}$?

How can one show that asymptotically $$\sum_{x=1}^\infty \prod_{i=1}^{x-1} \left(1-\frac{i}{n}\right) \sim \sqrt{\frac{\pi n}{2}} \; ?$$ A non rigorous argument is to say that for large $n$, ...
1
vote
2answers
46 views

Finding an approximation for the difference of $a_n = \frac{1}{1+a_{n-1}}$ and it's limit.

I've got the recurrence $\displaystyle{a_{n} = {1 \over 1 + a_{n - {\tiny 1}}},\ }$ for $0 < a_{0} < 1 $ which has the solution $\displaystyle{\alpha = {\,\sqrt{\, 5\,}\, - 1 \over 2}}$ I am ...
5
votes
1answer
107 views

Good resource/exercises for learning asymptotic analysis?

I am studying asymptotic methods right now; things such as mellin transform, inverse mellin transform, saddle point method, laplaces method, etc... and I get very frustrated because I can't get very ...
7
votes
3answers
141 views

Asymptotic for sum

How can I find formula for $\displaystyle{\sqrt[3]1 + \sqrt[3]2 + \sqrt[3]3 + \cdots + \sqrt[3]n}$ with an accuracy ${\rm O}\left(\, 1 \over \vphantom{\LARGE A}n^{5}\,\right)$ Is here we should use ...
11
votes
1answer
245 views

Upper bound for the widest matrix with no two subsets of columns with the same vector sum

Over at PPCG there is an ongoing contest going on to find the largest matrix without a certain property, called property $X$. The description is as follows (copied from the question). A circulant ...
0
votes
0answers
10 views

Asymptotics and function composition

In the following question: Big O and function composition It is explained that if $a, b, c, d$ are functions and $a = O(c), b = O(d)$ it doesn't mean that $a ∘ b = O(c∘d)$. However, what if we allow ...
1
vote
1answer
21 views

Asymptotic relation between specific binomial coefficient and exponential function

I need to determine the asymptotic relationship between the functions: $$f_1(n)={n\choose{\lfloor{n\over{2}}\rfloor}}, f_2(n)=7^{\sqrt{n}}$$ (I'm going to just assume $n$ is always even.) I've ...
3
votes
0answers
38 views

Does $\theta(n)$ = $1/x$ make any sense?

So, I asked this question on a discrete structures exam today, which I apparently didn't give enough thought to: $f(x) = (5x^2 + 6x + 2)/(x^3 + 4x^2 +x)$ Find the correct theta notation for the ...
0
votes
0answers
8 views

GRAM series and Logarithmic integral

due to the prime number theorem wouldn't we expect that the prime number counting function admits the approxiamtion $$ \pi (x)= \gamma +loglog(x)+ \sum_{n=1}^{\infty} \frac{log^{n}(x)}{n.n!.\zeta ...
1
vote
0answers
33 views

Order of magnitudes comparisons

I need your help with the following. I need to determine how to order (functions) the following : \begin{align} &f(x)=(x/2)^{(x/2)} \\ &g(x)=x! \end{align} Note: I got both of them are ...
4
votes
1answer
110 views

Growth of ratio based on sum of squared binomial identity

It is a well-known identity that $$\binom{n}{0}^2+\binom{n}{1}^2+\cdots+\binom{n}{n}^2=\binom{2n}{n}.$$ By symmetry of the binomial coefficients, this means the ratio ...
0
votes
0answers
23 views

Big-O Notation Division

There was a similar thread on this question, but I am still unsure about the answer. I am asked to show, $$ \frac{e^{(r-q)h}-e^{-\sigma\sqrt{h}}}{e^{\sigma\sqrt{h}}-e^{-\sigma\sqrt{h}}} = ...
0
votes
0answers
13 views

What are asymptotic upper and lower bounds for $T(n) = T(n-2) + 1/\lg n$?

What are asymptotic upper and lower bounds for $T(n) = T(n-2) + 1/\lg n$? As $T(n)$ is not applicable for Master theorem,so i go ahead with the recursion tree but there i am not able to solve for ...
2
votes
1answer
52 views

Number of words not having a subword of length k with only one letter

Let $f_k(n,t)$ be the number of words of length $t$ over the alphabet $\mathcal{A} = \{1,\ldots,n\}$ such that no word contains $i^k$ as a substring for $i \in \mathcal{A}.$ I am looking to find the ...
2
votes
1answer
79 views

Corollaries of Green-Tao Theorem?

there is already a good thread which discusses some corollaries of the Green-Tao Theorem, here: Constructing arithmetic progressions The question I was wondering about is of a similar flavor but ...
0
votes
0answers
30 views

Sort functions by their growth rate

So yesterday I had a mock exam and I failed an exercise. I'm trying to solve it but I definitely can't reach the solution. Here's the problem : Arrange the following functions in a list, so that ...
-1
votes
1answer
19 views

big $\Theta$ question dealing with $\log_2{n}$ and $\log_{10}{n}$

Show that $\log_{10}{n} = \Theta(log_2{n})$. I know that I have to show that 1) $\log_{10}{n} = O(\log_2{n})$ show: $\log_{10}{n} \le C * \log_2{n}$ and 2) $\log_2{n} = O(\log_{10}{n})$ show: ...
0
votes
0answers
14 views

Big theta question

Find a number $a$ with $s(n) = \Theta(a^n)$ for $s(n) = 1^{(n^2+200n+5)}$. I worked out that $a = 1$ and that $1^{(n^2+200n+5)} \le C * 1^n, C = 1, n = 0.$ So long as n $\ge$ 0 the right-hand side ...
0
votes
1answer
17 views

Big oh / big theta proof for the following

Find a number $a$ with $s(n) = \Theta(a^n)$ for $s(n) = (\log_2{10})^{(n-3)}$. I'm not quite sure how to proceed. I was having problems with another problem trying to figure out what it means to ...
0
votes
2answers
41 views

Why is Wolfram missing so many oblique asymptotes? (Not only about Wolfram in thread)

Few days ago I made a post, and to be frank I'm not sure if I'm even having this question in the right forum. But I'm also looking for information on if my thoughts are correct. Observe this little ...
0
votes
1answer
28 views

Big oh proof for a(n) using big oh hierarcy

So I'm given the following big-oh hierarchy (each sequence is big-oh of any seqeuence to its right.) $1$, $\log_2{n}$, ... , $\sqrt[4]{n}$, $\sqrt[3]{n}$, $\sqrt{n}$, $n\log_2{n}$, $n\sqrt{n}$, ...
0
votes
1answer
30 views

Proving big oh for a function

Find a $C$ and $k$ such that $\sqrt{n^2 - 1}$ = $O(n^k)$. My professor has stated that there are two different $k$'s. One from the problem statement and one from the definition of big-oh. I know that ...
0
votes
3answers
54 views

Finding the limit of: $\lim_{x\rightarrow +\infty}\left(x\arctan x-x\dfrac{\pi}{2}\right)$

$\lim_{x\rightarrow +\infty}\left(x\arctan x-x\dfrac{\pi}{2}\right)$ I just removed a lot of unnecessary text from this post. If anyone could tell me how to find this limit, without L'Hôpital's rule, ...
3
votes
1answer
23 views

Oblique asymptote for: $f(t) = \frac{t^2\arctan t}{t-4}$?

Say a function $$f(t) = \frac{t^2\arctan t}{t-4}$$ Obviously, this has a vertical asymptote at $t = 4$. However, the oblique asymptote, if there is one, I can't seem to find. What I do is I put the ...
1
vote
2answers
66 views

Find the leading order asymptotic behaviour of the integral

$$I(x) = \int_0^{\infty}e^{-t-\frac{x}{t^2}}dt \mbox{ as } x \mbox{ tends to infinity} $$ I know this has a moveable maximum so you need to make a substitution which transforms it into the integral: ...
1
vote
1answer
30 views

Calculate the leading order asymptotic behaviour (with two maxima)

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
1answer
22 views

How to prove this asymptotic bound? [closed]

Given that $0<a<b$, $f(n) \in O(n^a)$, prove that $f(n) \in o(n^b)$ (note there is a difference between big o and little o)
0
votes
0answers
11 views

Determining if f(n) is Big-O of g(n)

I'm currently learning Big-O notation but I'm having a lot of trouble understanding it. I'm working through some true/false exercises: 1) $log(k)$ is $O(k)$ 2) $klog(k)$ is $O(k^2)$ 3) $k^2$ is ...