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
2answers
58 views

Asymptotic form of an integral

I would like to find an asymptotic form of the following integral when $s \to \infty$ ($s$ and $w$ are positive) \begin{equation} \int_{0}^{\infty} dx ~ \sqrt{x^2 + wx} ~ e^{-ixs} \end{equation} I ...
2
votes
0answers
83 views

$f(x)\sim 1/x \implies (1+f(x))^x\to e$, but what family of functions maximizes the speed of convergence from below?

This problem is subordinate to finding out if $$\left(1+\frac{\log p_{n+1}}{p_n}\right)^{p_{n+1}/\log p_n},$$where $p_n$ is the $n$-th prime, never stabilizes above or below its limiting value, which ...
0
votes
1answer
59 views

Prove $\lim_{n \to \infty}$ $(1+\frac xn-o(\frac 1n))^n=e^x$ [duplicate]

We know that $\lim_{n \to \infty}$ $(1+\frac xn)^n=e^x$. How to prove that $\lim_{n \to \infty}$ $(1+\frac xn-o(\frac 1n))^n=e^x$? Attempt of the proof: Let $\epsilon>0$ $\exists n_0$ such that ...
2
votes
2answers
32 views

Asymptotic expansion of the complete elliptic integral of the first kind

The complete elliptic integral of the first kind is defined as $$K(k) = \int_0^{\pi/2} \frac{d x}{\sqrt{1 - k^2 \sin^2 x}}.$$ I would like to derive (at least the first term of) the asymptotic ...
0
votes
1answer
26 views

Multiplication of two asymptotic expansions

I have two functions $g, f:(0,\infty)\rightarrow \mathbb{R}$ with asymptotic power series as follows: For all $N\in\mathbb{N}:$ $$f(t) \sim \sum\limits_{n=0}^{N} a_n t^n + O(t^{N+1}) \text{ }\text{ ...
3
votes
2answers
2k views

Solve the Relation $T(n)=T(n/4)+T(3n/4)+n$

Solve the recurrence relation: $T(n)=T(n/4)+T(3n/4)+n$. Also, specify an asymptotic bound. Clearly $T(n)\in \Omega(n)$ because of the constant factor. The recursive nature hints at a possibly ...
2
votes
2answers
25 views

How to bound the tail of p-series

How can I asses $S_n = \sum_{j=n}^\infty\frac{1}{j^p}, p>1$ in terms of $n$, specifically can I get something like $$S_n = O(?)$$
5
votes
2answers
117 views

Asymptotics of $\int_{0}^{+\infty}\!\!\frac{dx}{\sinh^2(\epsilon \sqrt{x^2+1}) } $ for $\epsilon$ near $0$

How to find an asymptotic expansion, for $\epsilon$ near $0$, of the following integral $$ I(\epsilon):=\int_{0}^{+\infty}\frac 1{\sinh^2 (\epsilon \sqrt{x^2+1}) } {\rm d}x. $$ As $\epsilon ...
0
votes
0answers
14 views

an oscillatory integral with two parameters

Consider $$I(a,b)=\int_{\mathbb{R}}e^{i(ax^2+bx)}\psi(x)\,dx$$ where $\psi$ is smooth and supported in $\{x:|x|\in[1/2,2]\}$. How to control $I(a,b)$ in terms of $a$ and $b$? Moreover, is there an ...
1
vote
2answers
23 views

How to prove $\omega$ bound without using limit?

How to show $n^{3.4} - 2015n^{2} + 3$ $\in$ $\omega(n^{3})$ without using limit? According to the definition of $\omega$, $f(n)$ $\in$ $\omega(g(n))$ if and only if $\forall c > 0$, $\exists n_0$ ...
1
vote
1answer
60 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} ...
-1
votes
3answers
33 views

The curve $x^3-y^3=1$ is asymptotic t the line $x=y$. Find the point n the curve farthest from the line $x=y$. [duplicate]

The curve $x^3-y^3=1$ is asymptotic t the line $x=y$. Find the point in the curve farthest from the line $x=y$ This is just need of further details in this ...
2
votes
3answers
93 views

$u_n=\exp( n\log n-(n+\epsilon)\log(n+\epsilon))$

how can i show this sequence $u_n$ is divergent: $$u_n=\exp( n\log n-(n+\epsilon)\log(n+\epsilon))\quad n\in \mathbb{N}^*;\quad \epsilon \in (0,1)$$ My attempts: \begin{align*} u_n&=\exp( n\log ...
0
votes
1answer
40 views

How do I find the equivalence of the expression $e^{n\log(n)-(n+e)\log(n + e)}$?

We want to find equivalence of the expression $$e^{n\log(n)-(n+e)\log(n + e)}$$ Note that: $$\log(n+t)=\log\left[n\left(\frac{t}{n}+1\right)\right]=\log(n) + \frac{t}{n} ...
1
vote
1answer
54 views

If $f(n) = O(g(n))$ and $f(n) \not\in o(g(n))$, does $f(n) = \Theta(g(n))$?

If $f(n) = O(g(n))$ and $f(n) \not\in o(g(n))$, does $f(n) = \Theta(g(n))$? Well, this is just another algorithm's class HW question, but I don't seem to be able to figure out how to prove or ...
5
votes
1answer
42 views

Can $f(x+1) = f(x)^{\ln(x)}$ be expressed as integral transform $\int g(x,t) dt $?

Let $x$ be a real number. Can some real-analytic function $f$ that satisfies for $x>3$ :$f(x+1) = f(x)^{\ln(x)}$ be expressed by standard functions as an integral transform : $$f(x) = ...
1
vote
0answers
14 views

Is $f(n)=O(g(n))$ or $f(n)=\Omega(g(n))$ when $f(n) = (\log n)^{\log n}$ and $g(n) = n/\log n$?

I have showed that $f(n)=\Omega(g(n))$ in the following way. We assume that $${\log n}^{\log n} \leq n/\log n$$ $$\implies \log n \times \log \log n \leq \log n - \log \log ...
0
votes
0answers
19 views
1
vote
1answer
89 views

Asymptotic behaviour of a recurrence relation - How to solve

I'm going over a chapter in recurrence relations in preparation for job interviews and came across the following. I'd like to gain some better understanding of how to solve such a question. Find a ...
53
votes
1answer
1k views

Why are asymptotically one half of the integer compositions gap-free?

This is a longish post about something that has been haunting me for a while about a kind of restricted composition, namely gap-free and complete compositions. First, I will define the terms that are ...
1
vote
1answer
41 views

Can we deduce that $⌊r^{n}α⌋≃r^{n}α$ when $r→∞$?

Let $α∈(0,1)$ be an irrational number and let $n≥1$ be a fixed positive integer. For any $r>4$ we define the positive integer $$k=⌊r^{n}α⌋$$ where $⌊.⌋$ denotes the floor function. My question is: ...
1
vote
2answers
57 views

Finding big O of a function

How do I find Big O of function which are polynomial fractions $$f(x) = \frac {x^4 + x^2 + 1}{x^3 + 1}$$ The same question is posted here (Finding Big-O with Fractions) but i dont understand the ...
2
votes
2answers
70 views

Asymptotic expansion of double integral

Define $$G(\theta) = \int\limits_0^\infty \int\limits_0^{2\pi} \frac{r\,e^{-r^2/2t}}{\sqrt{1-(\sin\theta\sin r \cos\varphi + \cos \theta \cos r)^2}} \mathrm{d} r \,\mathrm{d} \varphi$$ Clearly, for ...
0
votes
0answers
48 views

Find a big-O estimate for $f(n)=2f(\sqrt{n})+1$

Is the answer from the below linked question correct for my question? Or does the differing of $+ \log(n)$ instead of $+1$ change the outcome of the master theorem? Similar question here
1
vote
3answers
47 views

How can you tell if you an algorithm has running time of $\log n$?

I would like an example of an algorithm (or pseudocode) that shows $\log n$ running time. I know what $n$ and $n^k$ running time looks like (simple nested loops) but what does $\log n$ look like and ...
2
votes
2answers
366 views

Calculating run times of programs with asymptotic notation

When calculating the run time of programs using asymptotic notation, I know how to set up the sums for things like for loops, but I'm getting stuck on summing them up. Sorry if this is a dumb ...
2
votes
0answers
22 views

Asymptotic behaviour of $\sum_{k=0}^\infty \frac{n^k}{(k!)^\nu}$

Let $\nu>0$ be fixed. I am interested in the asymptotic behaviour of the series \begin{equation*}s(n,\nu)=\sum_{k=0}^\infty \frac{n^k}{(k!)^\nu} \end{equation*} in the limit $n\rightarrow\infty$. ...
0
votes
1answer
62 views

How do i prove this inequality

Im trying to prove that $f(n)=an^2 +bn+c$ where $a,b,c$ are constants is $\Theta(n^2)$ through inequalities. $$0 \le c_1n^2 \le an^2 + bn + c \le c_2n^2 \text{ for all } n \ge n_0$$ The book gave an ...
2
votes
1answer
65 views

Find this limits $\lim_{n\to\infty}n^2\bigl(n(H_{2n}-H_{n}-\ln{2})+\frac{1}{4}\bigr)$

Question1: Find this limits $$\lim_{n\to\infty}n^2\left(n(H_{2n}-H_{n}-\ln{2})+\dfrac{1}{4}\right)$$ where $$H_{n}=1+\dfrac{1}{2}+\dfrac{1}{3}+\cdots+\dfrac{1}{n}$$ Question 2: ...
4
votes
1answer
315 views

Can a curve be an asymptote?

$f(x)=x^3+\frac{3}{x-1}$ This was the question given to me.I replied that $f(x)$ will have only a single vertical asymptote of $x=1$. My teacher told that there'll be be two asymptotes.One is the ...
0
votes
1answer
33 views

How to derive bounds for the $n$-th term of a subsequence of $\mathbb {N} $, knowing two functions “squeezing” the number of the terms below $x$?

Let $ a_n $ be the $n $-th term of an infinite strictly increasing subsequence of $ \mathbb{N}$ and denote with $\nu(x)$ the number of terms smaller than or equal to $x$. Assume also ...
4
votes
1answer
282 views

How to show how primorials grow asymptotically?

The primorial $p_n\# $ is defined as the product of the first $n$ primes: $$p_n\# = \prod_{k = 1}^n p_k.$$ Asymptotically, primorials grow like $$p_n\# = e^{(1 + o(1))n\ln n)}.$$ How does one derive ...
0
votes
0answers
31 views

Two closest sums of pairs of reciprocals

Trying to obtain a better bound for a problem from this bounty question, I obtained the following problem. Let $n\ge 3$ be a natural number. The problem is to estimate (in particular, asymptotically) ...
0
votes
1answer
14 views

for [ f(n) = Sum(1:n) , g(n) = n^2 ] , why does ( f isIn O(g) AND g isIn O(f) ) hold?

An exercise solution claims that for f(n) = Sum(1:n) , g(n) = n^2 it holds that f isIn O(g) and g isIn O(f). I don't understand why this is, as it seems to me that f isIn O(n) and g isIn O(1), ...
0
votes
1answer
33 views

Explain why $f = O(g)$ for $f(n) = (2^{n} + 2n^{2})^{1/5}$ and $g(n) = 4n^{5} + 8n + 2\log(n)$

I am working on a review for a test and I'm trying to figure out how to explain the following problem: Determine if the following statement is True or False. Briefly explain why: If $\,f(n) ...
1
vote
1answer
22 views

Getting tight asymptotic upper and lower bounds of product logs

Consider $$ E(n)=\log_2\left(\log_2 (4)\right) +\log_2\left(\log_2 (5)\right) ... \log_2\left(\log_2 (n)\right) $$ This is equal to $$E(n)= \log_2\left(\log_2 (4)*\log_2(5)*\log_2(6) ... ...
0
votes
1answer
54 views

How to order functions by their rate of growth?

I have the following functions. \begin{align} &7n^3 + 3n\\ &4n^2\\ &\frac{12\log(n)}{\log(n)}\\ &\frac{1}{n^2}+18n^5\\ &e^{\log\log n}\\ &2^{3n}\\ ...
0
votes
1answer
33 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
3answers
108 views

Big O notation and polynomials

I often see that the following polynomial can be written as such: $f(x) = 6x^4+3x^3+O(x^2)$ where the big O collects all the lower order terms. Yet, I also see this sometimes: $f(x) = ...
16
votes
2answers
305 views

$f=\underset{+\infty}{\mathcal{O}}\bigr(f''\bigl)$ implies that $f=\underset{+\infty}{\mathcal{O}}\bigr(f'\bigl)$.

Let $f\in\mathcal{C}^2(\Bbb{R},\Bbb{R})$ be a positive function such that $f=\underset{+\infty}{\mathcal{O}}\bigr(f''\bigl)$ does it implies that $f=\underset{+\infty}{\mathcal{O}}\bigr(f'\bigl)$? ...
5
votes
2answers
71 views

How find this sum $\sum_{k=0}^{n}\binom{n}{k}|n-2k|$ closed form or asymptotic behaviour?

Find the following series closed form or asymptotic behaviour $$\dfrac{\displaystyle \sum_{k=0}^{n}\binom{n}{k}|n-2k|}{2^n}$$ I use wolfram can't give the closed form: see wolfram ,so I think ...
1
vote
1answer
33 views

Asymptotic Growth: little o(n) versus $O(n^\alpha)$

Let $f(n) \geq 0$ be defined for all $n \in \mathbb{N}$. Suppose $f(n)$ is $o(n)$ and at the same time $f(n)$ is not $O(n^\alpha)$ for all $0 \leq \alpha < 1$. Is this necessarily a contradiction? ...
1
vote
0answers
28 views

Cumulative minimum of an Ornstein-Uhlenbeck process

Assume we generate a sample path $X_t$ from an Ornstein-Uhlenbeck distribution (i.e. a mean-reverting random walk), where $dX_t = −\rho(X_t − \mu)dt + \sigma dW_t$. For concreteness, take $\mu = 0$, ...
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
47 views

Asymptotic behavior of divergent $p$-series

I am intertested in the asymptotic scaling behavior of the divergent $p$-series $$ \sum_{k=1}^n \frac{1}{k^p} $$ for $0<p<1$, i.e., is there a closed-form sequence $a_n$ so that $$ \lim_{n \to ...
1
vote
0answers
18 views

Fitting curves by extrapolating known behaviours in certain limits?

I have been studying how a the rotation and translation of a sliding disc (think of it as a hockey puck) is affected by uniform friction. I encountered an integral that I was not able to solve, and ...
0
votes
0answers
22 views

Asymptotic analysis of Kac Formula

I am currently reading the paper How many zeros of a random polynomial are real?. I am having trouble understanding theorem 2.2. In this theorem, authors tries to estimate this integral $E_n = ...
0
votes
0answers
56 views

Big Oh Complexity of the algorithm “for $i=1$ to $z$, for $j = 1-X(i)$ to $Y(i)-n^2$ set $k=0$”

I've got a past paper algorithm question I'm trying to complete. I was hoping you could helped me, if so great if not then it's fine :P if you can keep in mind ironically (yep cs student) I'm not ...
0
votes
1answer
37 views

find an asymptotic expansion by using the Watson's theorem

I want to apply the Watson's theorem to find an asymptotic expansion for the function $$f(z)=\int_{- \infty}^{\infty} e^{-z \frac{y^{2}}{2}} \sin(y^{2})dy$$ (Assume $z \rightarrow \infty, z>0$). ...
0
votes
1answer
17 views

Graphic intersecting asymptotes

Sometimes graphics intersect the asymptotes(horizontal) of the function we plot and then they tend to the asymptote to infinity.What gives us the information whether the graph only tends to the ...