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
34 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
29 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(?)$$
0
votes
0answers
16 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
25 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
votes
3answers
37 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
96 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
57 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
44 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
17 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 ...
1
vote
1answer
113 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 ...
1
vote
1answer
43 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: ...
0
votes
2answers
93 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
95 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
57 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
51 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
508 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
23 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
71 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 ...
3
votes
1answer
71 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: ...
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 ...
5
votes
1answer
312 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 ...
1
vote
0answers
36 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
15 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
24 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
86 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
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
3answers
164 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
316 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
74 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
33 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
56 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
20 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
24 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
61 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
41 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
18 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 ...
0
votes
1answer
37 views

asymptotic expansion for Bessel function $I_0(z)$ in terms of Gauss hypergeometric functions ${}_2F_1$

On the Wikipedia page one can asympotoic formula of the Bessel function $$ I_0(z) \propto \frac{e^z}{\sqrt{2\pi z}} $$ On the Wolfram page there is a more detailed asymptotic formula for the Bessel ...
0
votes
1answer
31 views

Time complexity and Stirlings approximation

We have an operation that is $O(\sum_{i=1}^{n^2}\log(i))$. Is this valid?: $= O(\log (n^2!)) = \{\text{Stirling}\} = O(\log((n^2)^{n^2})) = O(n^2 \log(n^2)) = O(n^2 \log(n))$ If so, what's an ...
1
vote
2answers
50 views

How to prove the gaussian functions are linear independent?

Assume that I have N Gaussian functions with different means $\mu_i$ and variances $\beta_i$, How to prove $e^{-\beta_i(x-u_i)^2}$ are linear independent? 1$\le$i$\le$N
1
vote
4answers
66 views

Why do we have $u_n=\frac{1}{\sqrt{n^2-1}}-\frac{1}{\sqrt{n^2+1}}=O(\frac{1}{n^3})$?

Why do we have $u_n=\dfrac{1}{\sqrt{n^2-1}}-\dfrac{1}{\sqrt{n^2+1}}=O\left(\dfrac{1}{n^3}\right)$ $u_n=e-\left(1+\frac{1}{n}\right)^n\sim \dfrac{e}{2n}$ any help would be appreciated
1
vote
2answers
39 views

Deciding $\displaystyle o,\omega,\Theta$ notations

I have a question which I couldn't solve for about two hours. It goes like this: Let $\displaystyle f(n)=\left(\frac{n+3\ln(n)}{n}\right)^n \ ; \ g(n)=27^{\ln(n)}$. Fill the blank box with ...
6
votes
1answer
77 views

How does the size of the set $A(R) = \{(a,b) \; | \; a,b \in N \times N, \; \gcd(a,b) = 1, \; a^2 + b^2 \leq R^2\}$ grow?

How does the size of the set $$A(R) = \{(a,b) \; | \; a,b \in \mathbb{N} \times \mathbb{N}, \; \gcd(a,b) = 1, \; a^2 + b^2 \leq R^2\}$$ grow as a function of $R$? My try: It's clear that $|A(R)| ...
0
votes
1answer
25 views

Is $f(n)=\Theta(g(n))$ equivalent to the existence of the limit $\lim_{n \to \infty} \frac{f(n)}{g(n)}$?

Title pretty much says it all. I would think this should be true, but don't have much experience in this area of mathematics and don't know how to go about proving it.
8
votes
0answers
115 views

Integral Asymptotics for inhomogenous phase

I'm looking for asymptotics for an integral of the form: $$F(n):=\int_{1/2-i\infty}^{1/2+i\infty} e^{\phi(n,z)}dz$$ where $\phi(n,z)=(n-n^3)\log(1-z)+n^2\log(1+z)-n\log(z)$. One can solve for the ...
0
votes
1answer
46 views

asymptote vs extraneous values

I am having trouble understanding the difference between a rational function with an asymptote versus having extraneous solutions. What is the difference between the two, if there is. Aren't ...