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

Simplifying $f(x) = \left(x^{3} + 2x^{2} + O(x)\right)\cdot\left(1 + \frac{1}{x} + O\left(\frac{1}{x^{2}}\right)\right) $

Simplify $$f(x) = \Big(x^{3} + 2x^{2} + O(x)\Big)⋅\Bigg(1 + \frac{1}{x} + O\bigg(\frac{1}{x^{2}}\bigg)\Bigg) $$ as $x \to +\infty$. I am a bit stuck as to what to do with the three sets of ...
0
votes
0answers
13 views

Comparing functions

I wanted to make sure I had the correct understanding of the following big $O/\Theta/\Omega$ questions and I figured it would be better posted here than SO as it was more about comparing function. a) ...
0
votes
0answers
11 views

“Asymptotic” $\mathbb{R}$-algebras

Definition. By an asymptotic $\mathbb{R}$-algebra, I mean an $\mathbb{R}$-algebra $F$ of functions $\mathbb{R} \rightarrow \mathbb{R}$ satisfying: $$\mathop{\forall}_{f:F}\left[\left(\lim_{x ...
0
votes
0answers
17 views

What do we call the number that measures how good of an asymptote $g$ is to $f$, and what are the basic results about this number?

Suppose we have a (potentially very complicated) smooth function $f : \mathbb{R} \rightarrow \mathbb{R},$ and we're trying to approximate it (in the limit as the input value goes to $+\infty$) by a ...
1
vote
1answer
17 views

Large pairwise coprime sets

Say that a set $S\subseteq\Bbb N$ is pairwise coprime if every two elements of $S$ are relatively prime. Denote by $f(n)$ the size of a maximal pairwise coprime subset of $\{1,...,n\}$. What is ...
1
vote
1answer
18 views

Product property of Big O

Trying to prove: If $f(n)$ and $g(n)$ are both $O(h(n))$, then $f(n)*g(n)$ is $O(h^2(n))$. Understanding so far : The product of upper bounds of functions gives an upper bound for the product of ...
4
votes
1answer
57 views

Each number in $S\subseteq \{1,\ldots,2n\}$ does not divide another one, with $|S|= n$. In how many ways?

Let $f(n)$ be the number of subsets $S\subseteq \{1,2,\ldots,2n\}$ such that $|S|=n$ and $a$ does not divide $b$ whenever $a,b \in S$ are distinct. Can we evaluate $f(n)$, at least asimptotically? ...
0
votes
1answer
19 views

Asymptotic error expansion of global error for single step methods

My question refers to the proof of the following theorem, but it may suffice to just skip the theorem and continue with the problematic taylor expansion $(\ast)$: Let $f(t,y)$ and the single step ...
0
votes
2answers
47 views

How to show that $O(n^\frac{3}{4} \log n) = O(n)$?

I try to analyze LazySelect algorithm (finds kth order statistic of a set). One of the steps is to take a sample of $n^\frac{3}{4}$ elements and sort it. It seems like this sorting is linear relative ...
2
votes
0answers
59 views

Arithmetic progression of squarefree integers?

Let $x$ be a given positive integer. I'm intrested in the longest arithmetic progression of squarefree integers within the interval $(x,x^2)$. Both constructive and nonconstructive results. For ...
1
vote
2answers
57 views

Why is $\binom{2n}{n} \asymp \Theta \big(\frac{2^{2n}}{\sqrt{n}}\big)$?

I saw this statement : $$\binom{2n}{n} \asymp \Theta \bigg(\frac{2^{2n}}{\sqrt{n}}\bigg) \asymp \Theta\bigg(\frac{4^n}{\sqrt{n}}\bigg)$$ How did we go from the first statement to the second? I tried ...
2
votes
1answer
40 views

Estimate integral $\,\displaystyle\int_{0}^{\infty}\operatorname{sech}\left(\varepsilon x\right)\cos\left(kx\right)\,dx,\,$ with $\,k,\varepsilon>0$

$ \newcommand{\sech}{\operatorname{sech}} $ Is there any analytic/asymptotic way to estimate the value of the integral: $$ \int_{0}^{\infty} \sech\left(\varepsilon x\right)\cdot ...
1
vote
0answers
15 views

what happens when expansion parameter is of the order of dynamical variable itself?

Lets consider following differential equation, $\epsilon \frac{dy}{dt} = ....$ In principle one can use Method of matched asymptotic expansion or Method of multiple scales to solve such singular ...
1
vote
3answers
72 views

Missing steps: Show the sum of the first n positive integers is of order $n^2$

In Rowsen's Discrete Mathematics text, 6th edition. He has this problem as an example (#11) on page 190. His solution for obtaining a lower bound is to ignore the first half of the terms. He does the ...
3
votes
1answer
63 views

Does writing $f(x)\sim \ell$ have a sense?

If $\lim_{x\to a}f(x)=\ell$, is it correct to say that $f(x)\sim_a \ell$ ? I would say yes since $\lim_{x\to a}\frac{f(x)}{f(a)}=1$, but on a test I wrote $e^{-t}\sim_0 1$ and the corrector said that ...
2
votes
2answers
28 views

Asymptotic of $ \sum_{r=1}^{k} \frac1{r^{3/2}}$ - Generalized Harmonic Number

What is the asymptotic approximation of the following generalized Harmonic number as $k \to \infty$ ? $$H(1.5,k) = \sum_{r=1}^{r=k} \frac{1}{r^{1.5}}$$ (there is a similar question posted on ...
-2
votes
2answers
30 views

specifying an asymptotic function

Please help me out; I need to specify a function satisfying these conditions: $$ f(0)=1 \;\;;\;\lim_{x \to \infty}f(x)=0$$ Hopefully does there exist a simple answer? Thanks a lot!
2
votes
0answers
48 views

Approximate an integral with Bessel functions

Given $r,a,\lambda\in\mathbb{R}$, $r<a$, how can I find an approximate solution for the following definite integral? $$ \int_0^\infty J_0 (\lambda r)J_1(\lambda a)\frac{1}{\sqrt{n+\lambda^2 ...
1
vote
2answers
34 views

oblique asymptote problem

I can't resolve limit for oblique asymptote for: $$\frac{2x^2 e^{1/x}}{2x+1}-x$$ I've tried solving it by putting the common denominator but it's a bit confusing because the numerator is bigger then ...
0
votes
0answers
23 views

Simple question about asymptotic notation

I'm quiet new to the asymptotic world, so apology in advance if this question seems too trivial for you experts. Given $\frac{2kn2^{-k}}{E[X]}.$ As $k \sim 2\text{log}_{2} n$, the numerator is ...
-1
votes
1answer
35 views

Excercise about Big-O notation [closed]

This is an exam question with the answers already released. I've been trying to read up about it, but it doesn't seem to make any sense to me, so I was hoping someone would point out why the correct ...
0
votes
0answers
40 views

For any arithmetic progression $n \in \Bbb{N} : n \equiv b \pmod a$, the natural density is $\frac{1}{a}$?

This question comes from here (page 10). Given that $d(A) := \lim_{x\to\infty}\frac{1}{x}\sharp\{n \leq x : n \in A\}$, how do I get that: 1) $d(n \equiv b \pmod a) = \lim_{x\to\infty}(\left [ ...
0
votes
0answers
29 views

How to prove $x^m = O(e^x)$ for any $m \gt 0$?

My attempt: It's true for $m = 1$ clearly. Now assume true for $m=1\dots M-1$. Then $x = O(e^x)$ and $x^{M-1} = O(e^{M-1})$. Lemma: if $f = O(g)$ and $f' = O(g')$ then $ff' = O(gg')$. Proof: $f = ...
1
vote
2answers
31 views

Simple question, what is meant by 'as $x \to \infty$ the number of squares $\leq x$ is $\sqrt{x} + O(1)$?

For $x \to \infty$: the number of squares $n^2 \leq x$ is $\sqrt{x} + O(1)$. From here (page 6). More specifically, do they mean that... I'm confused now. I'm really not sure what they mean ...
3
votes
1answer
56 views

Calulate a limit involving $\zeta{(\zeta{(z)})}$

I'm currently trying to evaluate the following limit: $$ \lambda=\lim_{z\to\infty}{\left[2^z-\left(\frac{4}{3}\right)^z-\zeta{(\zeta{(z)})}\right]} $$ A look at numerical approximations suggests, that ...
-2
votes
0answers
50 views

BIG OH:$ f (x) = 3x^3 + 2x + 4$. One has

I have this question in my homework. Its an a multiple choice question and goes as following: Let $f (x) = 3x^3 + 2x + 4$. One has that $O(x^3)$ ** the answers have been checked with the teachers ...
3
votes
1answer
33 views

$\sum_{n \leq x} \frac{1}{n} = \int_{1}^x \frac{dt}{t} + O(1)$ help deriving it

On page 5 of: Probabilistic Number Theory by Dr.J¨orn Steuding, there's $\sum_{n=2}^{[x]} \frac{1}{n} \lt \int_{1}^{[x]} \frac{dt}{t} \lt \sum_{n=1}^{[x] - 1}$ Therefore integration yields: ...
0
votes
0answers
24 views

The function $g(x)$ is in $\Omega(x^c)$ as $x\rightarrow 0$ for all $c>0$. Does this imply that $\lim \inf_{x\rightarrow 0} g(x) > 0$?

Consider a function $g: \: \mathbb R^+ \mapsto \mathbb R^+ $. For any $c>0$ this function is in $\Omega(x^c)$ as $x\rightarrow 0$. That is, given $c>0$ there exist $L$ and $x_0$ such that $g(x) ...
7
votes
0answers
98 views

Bear of an integral

I have a pretty ferocious integral to solve, and would be over the moon if I were able to get some sort of analytic expression / insight for it. $$ I = \int_{r}^{\infty} r_0^{-5/2} W_{-i\alpha'/2, ...
10
votes
1answer
76 views

Asymptotic behaviour of log log sum

I am interested in the asymptotics of $$F(m) := \prod_{j=1}^m \log(j+1) = \exp\left(\sum_{j=1}^m \log \log(j+1) \right)$$ Is there anything known? If not I figure I will need some good bounds on the ...
1
vote
1answer
54 views

Asymptotic for $\int_{\mathbb{R}}e^{ik(sin x - x)}f(x)\, dx$

Suppose $f$ is a smooth compactly supported function supported in $[-\pi, \pi]$. The problem I am working on is to show that $$\int_{\mathbb{R}}e^{ik(\sin x - x)}f(x)\, dx = ...
2
votes
1answer
65 views

Upper bounding a tricky sum

For a problem in probability, I'm trying to find an upper bound for $$ \sum_{d=0}^k\binom{k}{d}\gamma^d(1-\gamma)^{k-d}\left(1-p^d(1-p)^{k-d}\right)^m$$ which will help me analyze what values of ...
0
votes
1answer
46 views

How to prove that $\left(\log \log n\right) \times \left(\log \log \log n\right) = Ω\left(\log n\right)$

Is $$\log \log n \times \log \log \log n = \Omega(\log n) $$ How can we prove it. Actually I'm trying to prove that $f(n) = \lceil(\log \log n)\rceil !$ is polynomially bounded. It means $$c_1 ...
0
votes
2answers
29 views

Prove or disprove the following asymptotic relations

$P(x) = 2^x$ Prove or disprove that $p(n^3 + 4) \in O\left(p\left(n^3\right)\right)$ $2^{(n^3 + 4)} \in O(2^{n^3})$ $\lim_{n \rightarrow \infty} \space \frac{2^{n^3 + 4}}{2^{n^3}}$ using ...
0
votes
0answers
19 views

Asymptotic form of Whittaker function

I am working with Whittaker functions for a project and have no experience with asymptotic analysis - how is the following expression, for $\kappa \rightarrow \infty$ through the real numbers ...
1
vote
1answer
39 views

Is this a correct proof that $\tau(n)$ is eventually smaller than any $n^{\delta}$, $\delta>0$?

Is this a correct proof that $\tau(n)$ is eventually smaller than any $n^{\delta}$, $\delta>0$? I'm not even sure about the statement, let alone the proof. Let's first proof this result: $\tau(n) ...
4
votes
1answer
71 views

Evaluating a function in a closed form

Let $$g(x)=\lim_{n\rightarrow\infty}\sqrt{n}\int_0^x z^2e^{n(\cos^2z-1)}\ \mathsf dz$$ Evaluate $g$ in closed form. The answer is right here: ...
0
votes
3answers
57 views

How to prove or disprove $n^{28} = O(2^n)$

Prove or disprove $n^{28} = O(2^n)$. My solution: $$\lim _{n \to \infty} \dfrac {2^n} {n^{28}} = \dfrac {2*2*2 \dots _{(n \ times)}} {n * n * \dots _{(28 \ times)}}$$ As $n \to \infty$, both the ...
4
votes
1answer
70 views

Average order of $\mathrm{rad}(n)$

Let $\mathrm{rad}(n)$ denote the radical of an integer $n$, which is the product of the distinct prime numbers dividing n. Or equivalently, $$\mathrm{rad}(n)=\prod_{\scriptstyle p\mid n\atop p\text{ ...
2
votes
2answers
57 views

Growth Rate $n\ln n$

I mistakenly posted this on MathOverflow. I hope this is a better place for it. I have been investigating a problem about sports teams and came across the function $n\ln(n)$. I want to see if I can ...
0
votes
1answer
26 views

What can we say about the distribution of the prime-power factors of a big factor-rich number?

Let us say that a positive integer is factor-rich if it has more factors than any smaller integer. For example, $60$, which has twelve factors, is factor-rich; and therefore $72$, which also has ...
6
votes
1answer
174 views

The asymptotic of the number of integers that are sums of three nonnegative cubes

Let $c(n) $ be the number of distinct integers between $0 $ and $n $ of the form $ a^3 + b^3 + c^3$, meaning the sum of $3$ nonnegative cubes. $C(n) = O( n \space \ln(n)^x ) $ Find and prove the ...
7
votes
0answers
104 views

Counting the size of the largest sets of independent strings

This question derives from a PPCG coding challenge I posed previously. For a given positive integer $n$, consider all binary strings of length $2n-1$. For a given string $S$, let $L$ be an array of ...
0
votes
1answer
23 views

Proving the asymptotic relationship between two functions

I was playing around with numbers a few days ago and found an asymptotic approximation to two functions: $$y=-\ln{x}$$ And $$y=x^{1-\frac{1}{x}}-x$$ Can I have a proof that it is (or isn't) ...
9
votes
2answers
216 views

Fourier transform of $\Gamma \left (\frac{1}{2}-i \frac{p}{2 \pi} \right) /\sqrt{ \cosh(p/2)}$

Is it possible to compute the following Fourier transform analytically? $$\psi(x) = \frac{1}{\sqrt{4 \pi}}\int \Gamma \left (\frac{1}{2}-i \frac{p}{2 \pi} \right) \frac{e^{i p x}}{\sqrt{ \cosh(p/2)}} ...
0
votes
0answers
13 views

Proving that an asymptotic series is uniform for parameter belonging to a compact subset of the parameter space.

Let $U$ be a disk centered at $z=1$ of radius $\delta$. Given the function $h(z)=\frac{1+i(z^2-1)^{1/2}\sin(\alpha/2)}{1-i(z^2-1)^{1/2}\sin(\alpha/2)}$, define the function $$w(z)=\frac{1}{2}\ln h(z) ...
3
votes
1answer
49 views

What does this use of little-o notation mean?

I am currently going through the proof of Prime Number Theorem, as given in Hardy and Wright, and in it they define the following constant: $$\alpha = \limsup_\limits{x \to \infty} \left|V(x) ...
0
votes
1answer
58 views

Limit of Quotient of two functions changed by constant amount

Let $f(x), g(x)$ be two function's, how to show that $$ \limsup_{x\to a} \frac{f(x)}{g(x)} = \limsup_{x\to a} \frac{f(x)}{g(x) + c} $$ for $a \in \mathbb R \cup \{ \pm \infty \}$ and $c \in \mathbb ...
2
votes
1answer
44 views

Alternative geometric interpretation for big-o and little-o

I understand that, in big-o notation, when we say that a function $f$ is $O(x^2)$ we're basically saying that $$|f(x)|\le M |x^2|$$ for some constant $M>0$ and for all $x>x_0$ for some ...
1
vote
0answers
38 views

Compare growth of function and derivative

Suppose $f:\mathbb R \rightarrow \mathbb R$, $O(1)<f(x)<O(x)$ (i.e. has slower than linear growth but is unbounded), $\lim_{x\rightarrow \infty} f'(x)=0$ and $f'$ is monotonic. Is it possible to ...