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
3answers
232 views

Is there a function thats not in Big O and not in Big Omega?

I've been thinking about this problem for a while now but I can't fully come up with an example. It would make sense that this would exist and the only way I think it would work is if the functions ...
8
votes
1answer
110 views

Asymptotics of $\prod_{x=1}^{\lceil\frac{n}{\log_2{n} }\rceil} \left(\frac{1}{\sqrt{n}} + x\left(\frac{1}{n}-\frac{2}{n^\frac{3}{2}} \right)\right) $

I am trying to work out the large $n$ asymptotics of $$S_n = \prod_{x=1}^{\lceil\frac{n}{\log_2{n} }\rceil} \left(\frac{1}{\sqrt{n}} + x\left(\frac{1}{n}-\frac{2}{n^\frac{3}{2}} \right)\right) .$$ ...
0
votes
1answer
14 views

General or specific property? $(1-p)^{-x^2} = x^2 p + \mathcal{O}(p^2)$

As told in the title, I found this equality: $$(1-p)^{-x^2} = x^2 p + \mathcal{O}(p^2)$$ and wonder whether this is true in general or whether it does only hold in the context I've seen it. It comes ...
1
vote
1answer
44 views

big $\mathcal O$ for number of prime in an interval?

According to von Koch 1991, if the Riemann hypothesis is true, then the for the prime counting function $$\pi(x)=Li(x)+\mathcal O(\sqrt x \log x)$$ I am trying to understand how to deal with the ...
1
vote
2answers
31 views

Prove $8n^{3}$ $+$ $√n$ $∈$ $Θ$($n^{3})$

just wondering if I proved this question correctly. Any hints, help, or comments would be appreciated. There are two cases to consider to prove $8n^{3}$ $+$ $√n$ $ϵ$ $Θ(n^{3})$ $8n^{3}$ $+$ $√n$ $ϵ$...
0
votes
1answer
77 views

Big Oh notation involving $\log n!\in O(n\log n)$

I have worked hard on these questions and have found my own approach. I'm just checking if it makes logical sense for others and works. I'd appreciate any hints or better approaches. Question 1: ...
1
vote
1answer
47 views

The asymptotic behavior of $\sum_{n=1}^\infty\frac{1-\cos(x4^n)}{2^n}$ as $x\to 0$

Is there a way to show that for small $x$'s $$\sum_{n=1}^\infty\frac{1-\cos(x4^n)}{2^n}\le c\sqrt x$$ I tried Taylor expansion of $\cos$ and square root... Thank's
0
votes
1answer
50 views

Counting function for the number of zeros of a continuous positive function?

Let $f(x)$ within $x\in[a,b]$ an absolute continuous function with $f(x)\geq0$ $f(x_m)=0$ for all absolute minima $x_m$ no other zeros than at $x_m$ I am trying to define a counting function for ...
2
votes
0answers
45 views

Asymptotics for the Alternating Mertens Function

Are there any tight bounds, or any nontrivial ones actually, known for, with the lack of a better name, the Alternating Mertens Function: $$ S(n) = \sum_{k=1}^{n} \left((-1)^k \mu\left(k \right)\right)...
1
vote
0answers
39 views

Asymptotic behavior of the solution of a 2nd order linear ordinary differential equation

In studying the harmonic oscillator, we encounter the equation $$ f'' +(2E - x^2) f = 0$$ What is the asymptotic behaviour of the solution to this equation for a generic $E$? Any good book on ...
4
votes
5answers
117 views

Limit of $\sqrt[n]{(x+1)…(x+n)} - x$ as $x \to +\infty$

Let $n \in \mathbb{N}^{\ast}$. I want to determine the following limit : $$ \lim \limits_{x \to +\infty} \sqrt[n]{(x+1)\ldots(x+n)} - x.$$ Let $x = \frac{1}{t}$ with $t \to 0$. It is equivalent to ...
4
votes
0answers
155 views

Heat equation, boundary gradient singularity

Consider the Cauchy-Dirichlet problem for the heat equation in a non-cylindrical region $\Omega \subset \mathbf{R}^+ \times \mathbf{R}$: $\Omega = \{ (t,x): \; 0 \leq t \leq 1, \; x \leq (1-t)^\...
12
votes
4answers
238 views

An equivalent for $\sum_{n=0}^{\infty} e^{-x\sqrt{n}}$ as $x$ tends to $0^+$

I would like to obtain an equivalent form for $$ f(x)=\sum_{n=0}^{\infty} e^{-x\sqrt{n}} $$ as $x \rightarrow 0^+$. I tried without success to "remove" the $\sqrt{\cdot}$ in the summand by summing ...
0
votes
1answer
134 views

Find the leading order uniform approximation when the conditions are not $0<x<1$

$$\epsilon y''+y'\sin x+y\sin 2x = 0$$ with boundary conditions $y(0)=\pi$ and $y(\pi)=0$ as $\epsilon \rightarrow 0$. I don't know how to find out where the boundary layer is? I thought initially it ...
1
vote
0answers
25 views

Find the leading order uniform approximation to the boundary value problem $\epsilon y''+y'\sin x+y\sin 2x = 0$? [duplicate]

$$\epsilon y''+y'\sin x+y\sin 2x = 0$$ with boundary conditions $y(0)=\pi$ and $y(\pi)=0$ as $\epsilon \rightarrow 0$. I don't know how to find out where the boundary layer is? I thought initially it ...
0
votes
1answer
27 views

A probably simple big $\mathcal{O}$ question

I have a probably simple big $\mathcal{O}$ question. Is the following statement correct? $$\mathcal{O}(x \log x)=\mathcal{O}(\sqrt x \log x)$$ why?
9
votes
2answers
122 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 \\ \text{gcd}(k,n) = 1 }} \frac{1}{n^s}$$ in such a way that I can find an ...
2
votes
0answers
69 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
149 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 $(1+...
1
vote
1answer
49 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
42 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 ...
1
vote
1answer
366 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: $$S_k=\sum_{n=1}^{k^2-...
4
votes
1answer
75 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 $f(...
1
vote
1answer
37 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
37 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 ...
1
vote
1answer
890 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
40 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
40 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 ...
1
vote
1answer
78 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 ∞} \frac{(\...
3
votes
2answers
144 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 solution?...
2
votes
0answers
49 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 $c_{k}=(\...
0
votes
1answer
55 views

Growth function big theta

a) Show that $3x+7$ is $\Theta(x)$. b) Show that $2x^2 +x -7$ is $\Theta(x^2)$ $2x^2+x-7 \geq x^2$ for $x \geq 2$ if $x \gt 1$ $x^2 \gt x$ $2x^2 \gt 2x$ $x^2 \gt 1$ $x^2\geq x^2$ c) Show ...
1
vote
0answers
31 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
62 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
73 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.
6
votes
2answers
89 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-i/n)...
1
vote
2answers
59 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 ...
8
votes
1answer
588 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
201 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 ...
13
votes
1answer
284 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 ...
1
vote
1answer
113 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
1answer
67 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 ...
1
vote
0answers
40 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
124 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 $$\dfrac{\binom{2n}{n}}{\binom{n}...
2
votes
1answer
181 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 ...
3
votes
1answer
146 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 isn'...
-1
votes
1answer
27 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
1answer
29 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
52 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
37 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}$, $n^2$...