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
11 views

How to prove that $\omega (n) = O\Big{(} \frac{\log(n)}{\log(\log(n))}\Big{)}$ as $n \to \infty$?

Let $$\omega(n) := \text{number of distinct primes dividing } n. $$ How can one prove that $\omega (n) = O\Big{(} \frac{\log(n)}{\log(\log(n))}\Big{)}$ as $n \to \infty$? I know that $\omega(n)! \leq ...
0
votes
0answers
10 views

Problem in understanding the proof of master theorem case

I am going through the proof of master method or master theroem. This is the formula that is been given by the author for the Total Work =Cn^d*(∑(a/b^d)^j) where value of J=0 to logbn as per the ...
0
votes
3answers
31 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 ...
6
votes
1answer
69 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
11 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 ...
0
votes
0answers
20 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
16 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
29 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
42 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
29 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 ...
0
votes
0answers
32 views

Asymptotics of Hypergeometric series

Suppose we have a $_pF_q$ hypergeometric series that terminates for all $r>t$ for some positive integer $t$, and consider the expression \begin{multline*}\lim_{n\to\infty} ...
2
votes
0answers
29 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 ...
1
vote
0answers
24 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
102 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 ...
1
vote
0answers
26 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 ...
13
votes
3answers
126 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
54 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
19 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
25 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?
4
votes
2answers
127 views
+100

the first $2k$ terms of the power series of $\sec x + \tan x$ at $x=-\pi/2$

We know the power series of $\sec x+\tan x$ is as follows, $f(x)=\sum_{n\geq 0}\frac{E_n}{n!}x^n$, where $E_n$ is Euler Zigzag numbers and clearly the radius of convergence of $f(x)$ is $\pi/2$. ...
8
votes
2answers
78 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 ...
1
vote
0answers
46 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
39 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
19 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
35 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
46 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
22 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) [closed]

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
29 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
24 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
20 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
36 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
61 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
62 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
20 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
37 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
70 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
75 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
50 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
113 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
143 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
255 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
39 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 ...