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

learn more… | top users | synonyms (1)

3
votes
1answer
60 views

Given a set of powers of two, how “close” can we come to a prime?

Given a natural $n \ge 2$, we can construct a set of all powers of two from $2^n$ to $2^{4n}$: $$\{2^n, 2^{n+1}, 2^{n+2}, \dots, 2^{4n}\}$$ How close does one of these numbers come to a prime in the ...
7
votes
0answers
93 views

Given the first $n$ primes, find the least common multiple of $p_1 - 1$, $p_2 - 1$, …, $p_n - 1$

Given the first $n$ primes, we can label the $k$th prime as $p_k$. So, what is the least common multiple(LCM) of {$p_1 - 1$, $p_2 - 1$, $p_3 - 1$, ..., $p_n-1$}? In other words, if we subtract $1$ ...
3
votes
2answers
137 views

Asymptotic development of a recurrent sequence

Let $u_0 = 1$ and $u_{n+1} = \frac{u_n}{1+u_n^2}$ for all $n \in \mathbb{N}$. I can show that $u_n \sim \frac{1}{\sqrt{2n}}$, but I would like one more term in the asymptotic development, something ...
0
votes
1answer
27 views

BigOh Complexity: $\frac{x^{3} + 2x}{2x + 1}$ is $O(x^2)$?

Show $\frac{x^{3} + 2x}{2x + 1}$ is $O(x^2)$ Can I do it like this? Since exponent rules/laws allow this: $\frac{x^{3} + 2x}{2x + 1}$ $=$ $\frac{1}{2}x^{2} + 2x$ Must show a constant c>0 and k ...
0
votes
0answers
25 views

When can you replace by an equivalent in a sum or inside some given function?

This question is a follow-up to this question. I was originally going to post it as a comment to robjohn, but decided it should grow into a question of its own. Write $a_n\sim b_n$ if $\lim ...
2
votes
1answer
85 views

Improvements of Dusart's lower bound for $ e^\gamma \log x \prod_{p\le x} \frac{p-1}{p}$.

Let $\gamma$ be the Euler-Mascheroni constant. In this paper (Theorem 6.12) it is proved that for $x\ge 2793$, $$ e^\gamma \log x \prod_{p\le x} \frac{p-1}{p}> 1-\frac{1}{5 \left(\log ...
1
vote
0answers
11 views

Strategies for approximating fourier transform of $k$-th power of the $n$-th derivative of a function

For a function $f(x)$ with Fourier transform $\hat{F}(q)$, I'm interested in understanding the relationship of the Fourier transform of a power of a derivative of $f$ to $\hat{F}(q)$. Explicitly, I ...
0
votes
1answer
9 views

Asymptotic distribution of ratio / multiplication of two variables

Suppose $\rightarrow_D $ denotes convergence in distribution. If we know $$ f_1 \rightarrow_D W_1 $$ $$ f_2 \rightarrow_D W_2 $$ Can we say something about the convergence of $$ f_1 f_2 ...
0
votes
0answers
28 views

Orders of growth of typical sequences

It's been a while since I had to deal with some sort of asymptotic analysis so I am a bit rusty and trying to get the basics back together. Since I don't really know where to look for these things, I ...
1
vote
0answers
40 views

Approximate solutions for quintic equation

The other day I asked a question in here about deriving the equations $$u^2\left(\left(1-s_1\right)+3u+3u^2+u^3\right) =\alpha\left(s_0+2s_0u+\left(1+s_0-s_1\right)u^2+2u^3+u^4\right),$$ where ...
1
vote
1answer
30 views

Proving Lower Bound on Catalan Numbers

I'm a student of computer science and was reading through my algorithms textbook about matrix chain multiplication. It brought up Catalan numbers and I was hoping to prove the lower bounds on it. This ...
3
votes
2answers
62 views

Sum of 'inverse' Normal (1/X) random variables. Equivalent resistance calculation

Consider the case of $N$ resistances $R$ connected in parallel. The equivalent resistance of such a circuit is calculated as follows $$ \frac{1}{R_{eq}} = \underbrace{\frac{1}{R} + \frac{1}{R} + ...
1
vote
0answers
28 views

Mutual Asymptotic analysis of the given fucntions

$ f(n)$ = $ 3n^{\sqrt{n}} $ $g(n)$ = $2^{\sqrt{n}log_2n}$ $h(n)=n! $ For all the $3$ pairs of the functions, which one is $Big-O$ of which ? I am unable to compare these functions. Edit : I ...
9
votes
3answers
104 views

A series involving $\prod_1^n k^k$

Is this series $$\sum_{n\geq 1}\left(\prod_{k=1}^{n}k^k\right)^{\!-\frac{4}{n^2}} $$ convergent or divergent? My attempt was to use the comparison test, but I'm stuck at finding the behaviour of ...
0
votes
3answers
42 views

Notation for asymptotic approximation

I was reading Stirling's approximation and got quite confused with the idea of asymptotic formula. So in Wikipedia it says that a function $F(n)$ of $n$ is asymptotic formula for $P(n)$ if $P(n)$ is ...
-1
votes
2answers
47 views

A function whose graph has vertical asymptotes at $x=+2$ and $x=-2$, and a horizontal asymptote at $y=0$

Determine a function whose graph has vertical asymptotes at $x=+2$ and $x=-2$, and a horizontal asymptote at $y=0$? I don't know to satisfy these conditions.
1
vote
1answer
65 views

Which is the greatest integer value of $a$, for which $A'$ is asymptotically faster than $A$?

The recurrence relation $T(n)=7T\left( \frac{n}{2}\right)+n^2$ describes the execution time of an algorithm $A$. A "competitor" algorithm, let $A'$, has execution time $T'(n)=aT'\left( \frac{n}{4} ...
0
votes
0answers
42 views

Check if $2^{2^n}=O(2^n)$

I want to check if $2^{2^n}=O(2^n)$. That's what I have tried: Let $4^n=O(2^n)$. Then, $\exists c_1>0, n_1 \in \mathbb{N}$ such that $\forall n \geq n_1$: $$4^n \leq c \cdot 2^n$$ $$$$ ...
0
votes
1answer
41 views

How can we show that $\lim_{n \to +\infty} f(n)=+\infty$?

We suppose that $\lim_{n \to +\infty} f(n)=+\infty$. I want to prove that if $f(n)=O(g(n)), c \in \mathbb{R}$, then $f(n)+c=O(g(n))$ . $f(n)=O(g(n))$ That means that $\exists c_1>0, n_2 \in ...
0
votes
1answer
73 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
3answers
44 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
100 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
13 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
1answer
36 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
27 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
50 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
44 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
32 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
44 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
35 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
30 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
111 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
39 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
164 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
90 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
20 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?
8
votes
2answers
86 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
53 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
47 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
20 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
36 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
61 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
56 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
29 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 ...
1
vote
1answer
177 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
25 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
23 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
38 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 ...