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

learn more… | top users | synonyms (1)

2
votes
1answer
31 views

asymptotics of this sum $ x \to 0 $

given the sum $$ \sum_{n=0}^\infty \frac{\exp(-nx)}{n+a} =f(x) $$ what would be the asymtptic of this series ?? for $a=1$ i believe this series goes as $ f(x) \sim \frac{1}{x}+ \gamma $ for every ...
1
vote
1answer
47 views

Bound summation of successive square roots

What is a tight upper bound for $f(n)$ where $f(n) = f(\sqrt{n}) + \frac{1}{n}$. One can easily find the following upper bound $O(\lg \lg n)$, however I'm interested in a tight bound. Regards.
1
vote
0answers
25 views

Big-O Notation for remainder terms in Taylor expansion

The Big-O notation is commonly used in Taylor expansions of the form $$f(x+\epsilon)=f(x)+\epsilon f'(x)+O(\epsilon^2)$$ to say that the remainder term grows at least quadratic around $\epsilon=0$. ...
1
vote
1answer
45 views

Prove or disprove: $(\frac{1}{n})^n(1 - \frac{1}{n})^{n^2-n} \simeq \frac{1}{n!}$ as $n \rightarrow \infty$.

Prove or disprove: $(\frac{1}{n})^n(1 - \frac{1}{n})^{n^2-n} \simeq \frac{1}{n!}$ as $n \rightarrow \infty$. I'm trying to prove the statement by building on my observation that $(1-\frac{1}{n})^n$ ...
3
votes
0answers
63 views

Question about Big O notation for asymptotic behavior in convergent power series

Examples of such use of Big O notation can be found for instance on Wolfram Alpha here. More details on the Wikipedia page. The idea, as I understand it, is that the term between parenthesis in Big O ...
2
votes
0answers
34 views

Question about Big O notation for asymptotic behavior in convergent power series [duplicate]

Examples of such use of Big O notation can be found for instance on Wolfram Alpha here. More details on the Wikipedia page. The idea, as I understand it, is that the term between parenthesis in Big O ...
0
votes
1answer
22 views

Interpreting expression with big-O notation in the exponent ($f(x) = x^{1+O(1)}$)

How should one interpret the notation $f(x) = x^{1+O(1)}$? I'm a bit confused as to what this means. Does it merely suggest that f(x) grows as some integer power of x?
0
votes
2answers
20 views

Big Omega — n, n + 100

Given $f(n) = n$ and $g(n) = n + 100$, it seems that f(n) is $O(g(n))$ when $C = 1$ and $k= 0$. That is, for every $n$ from $0$ to infinity, g(n) is strictly larger than f(n). Now, concerning ...
1
vote
1answer
35 views

Integral $\int_{-\infty}^\infty dx e^{-nx^2/2}(z-ix)^n$

$$ I\equiv\mathcal{F}_n(z)=\int_{-\infty}^\infty dx e^{-nx^2/2}(z-ix)^n. $$ Evaluate I for $n \to \infty$ and z real. We can consider $z\geq 0$ due to the symmetry of $\mathcal{F}$ given by $$ ...
-2
votes
0answers
23 views

prove that θ(n-1)+ θ(n)= θ(n)

I need to prove that statment with big Theta defenition.. θ(n-1)+ θ(n)= θ(n) I have tried many things but cant prove that with defenition of theta
-1
votes
1answer
36 views

Prove that |O(2n)-O(n)|=O(n)

I need to prove that statement with the defenition of big O |O(2n)-O(n)|=O(n) Does it can be proven? or not? if i can, so how..in which way? i tried almost ...
0
votes
2answers
34 views

Big-O notation and polynomials

In my text, I am given that the sum of the first n positive integers can be understood in terms of big-O notation. ''Since each of the integers in the sum of the first $n$ positive integers does not ...
0
votes
0answers
30 views

Free lecture notes to Carl Bender's Mathematical Physics video lecture course?

I am just watching Carl Bender's Mathematical Physics video lecture course (about asymptotics and its application in physics) http://www.perimeterscholars.org/328.html which is great! Are there any ...
4
votes
3answers
67 views

Taking Limits with Binomial Coefficients

I am interested in taking the following limit: \begin{equation} \lim_{n \to \infty}\frac{{n/2 \choose m}}{n \choose m}. \end{equation} Provided that $m$ is fixed the solution is: \begin{equation} ...
0
votes
2answers
51 views

Expanding $\ln(1+f(x))$ around $f(x)=0$ when we do not know whether there is an $x$ such that $f(x)=0$.

I want to expand $\ln(1+f_T(x,\theta))$ about $1+f_T(x,\theta)=1$. What I have in mind is something like $$ \ln(1+f_T(x,\theta))=\ln(1)+f_T(x,\theta)-\frac{1}{2} \frac{1}{1+\tilde{f}} ...
0
votes
0answers
13 views

How to determine sub-exponential time growth?

I'm a little bit confused of sub-exponential time growth; consider the definition from Hoffstein's book An Introduction to Mathematical Cryptography: Given input of $k$ bits, then if an algorithm ...
1
vote
0answers
42 views

Integral asymptotics

Is there some kind of a variation of the Laplace's method or some other formula for the asymptotics of integrals of a type $$\int_a^bf(x)e^{mp(x)}\cos(mq(x)+x/2)dx, \ m\to\infty.$$ Here $f,p,q$ are ...
0
votes
1answer
20 views

Prove the following $\frac{\Omega(f(n))}{\Omega(g(n))} \subseteq \Omega(\frac{f(n)}{g(n)})$

I want to prove the following: $$\frac{\Omega(f(n))}{\Omega(g(n))} \subseteq \Omega(\frac{f(n)}{g(n)})$$ I wonder if its true? What about using $n$ and $n^2$? Any suggestions? Thanks!
2
votes
1answer
26 views

Big O notation preserved under convex functions?

Suppose that the random variable $X_T$ is $O_p(1)$ as $T \rightarrow \infty$, i.e. $\forall \epsilon>0$, $\exists M_\epsilon>0$ such that $\mathbb{P}(X_T>M_\epsilon)<\epsilon$ $\forall T$. ...
0
votes
1answer
13 views

Order functions by speed of their asymptotic growths

We are given list of functions. Task is to sort it by the speed of their asumptotic growth in ascending order. Yes, it's a homework. I already spent some solid amount of time calculating limits. I ...
1
vote
1answer
76 views

What is $O\Big((n+1)!\Big)$?

What is $f(n) = (n+1)!$ which is also $f(n) = (n+1)n!$ in terms of big-O notation? My guess is $O(n \cdot n!)$ but I am not sure. I only know it is certainly $f(n) \in O(n^n)$.
5
votes
2answers
84 views

Use the Euler-Maclaurin summation formula to estimate a summation

$\sum_{k=0}^n \frac{1}{1+\frac{k}{n}}$ How can we estimate it to order $O(n^{-5})$ ?
0
votes
0answers
22 views

Asymptotic distribution of the t statistic

I want to find the asymptotic distribution of the t statistic when (a) we assume equal variances between groups with sample sizes m and n (b) assume unequal variances between groups For part (a) it ...
0
votes
1answer
19 views

Tight bound of worst case performance of algorithm

I am trying to find the "tight bound of an algorithm for the worst case run time. I have found that the upper bound of the worst case is O(n), I have also found that the lower bound for the worst case ...
1
vote
0answers
37 views

Is $\log^* (n+1)^{n+2} \in O(\log^* n)$?

I would like to know if $\log^* (n+1)^{n+2} \in O(\log^* n)$, where $\log^*$ is the iterated logarithm. I tried doing: $ \log^* (n+1)^{n+2} =\\ \log^{*}(\log(n+1)^{n+2})-1 =\\ \log^{*}((n+2) \cdot ...
0
votes
2answers
37 views

Asymptotics - Big Omega

I have a question about Asymptotics involving big Omega... How do I need to approach this equation in order to prove it? $$n \cdotΩ(f(n)) = Ω(n\cdot f(n))$$ Thank you very much for your answers!
4
votes
0answers
52 views

Closed form or asymptotic expansion for $\int_0^m \frac{n^x}{\Gamma(x+1)}dx$?

$$\int_0^m \frac{n^x}{\Gamma(x+1)}dx:n,m \in \mathbb{R}$$ I'm dubious as to whether there's a closed form for the above, if there is I'll be very happy. Otherwise: Is there a closed form for ...
0
votes
1answer
55 views

Prove $\Omega(f(n)) \subset \Omega(g(n)), iff : g(n)\in \mathcal{O}(f(n)) \wedge f(n) \not\in \mathcal{O}(g(n))$

I want to prove the following $$\Omega(f(n)) \subset \Omega(g(n)), iff : g(n)\in \mathcal{O}(f(n)) \wedge f(n) \not\in \mathcal{O}(g(n))$$ What I did so far is: $$t(n)\in\Omega(f(n)) \rightarrow ...
1
vote
0answers
22 views

Asymptotic estimate for an expression of

\begin{equation} A = \frac{(\frac12-\frac{1}{n})(\frac12-\frac{2}{n})...(\frac12-\frac{t-1}{n})}{(\frac{1}{2}+\frac{1}{n})(\frac{1}{2}+\frac{2}{n})... (\frac{1}{2}+\frac{t}{n})} \end{equation} Can we ...
2
votes
1answer
39 views

asymptotic estimate for this expression

How can I compute an asymptotic estimate for following expression? \begin{equation} A = ...
0
votes
0answers
23 views

asymptotic estimate for binomial coefficient

How can we compute the asymptotic estimate for binomial coefficient $Q = \binom{n}{s-t}$ with the $n,s \gg 1$ and $ t \ll n$ and $ t \ll s$
0
votes
0answers
15 views

How to compute an asymptotic expansion for $\sum_{i \ge 0} a_in^{-i} $ to a relative error of $O(n^{-2})$? [duplicate]

How to compute an asymptotic expansion for $\sum_{i \ge 0} a_in^{-i} $ to a relative error of $O(n^{-2})$
3
votes
1answer
61 views

On the sum of prime powers

Has anybody investigated the asymptotic growth rate of functions in the form of $$f(z,n)=\sum\limits_{p\le n}p^z$$ For $Re(z)\ge -1$. Of course $f(0,n)=\pi (n)$ has an ocean of research surrounding ...
2
votes
1answer
42 views

Compute summation with a relative error of O(n^-2)

$a(n) = \sum_{i \geq 0} a_i n^{-i}$, how can we compute the value of $a(n)^n$ with a relative error of $O(n^{-2})$?
0
votes
0answers
19 views

asymptotics big Omega and O

I have a problem at Asymptotycs.. there is given to me that : $$f(n)+g(n) \in \Omega(t(n))$$ I need to prove with the defenition that: $$\operatorname{abs}(f(n)-g(n))∈O(t(n))$$ How I start ...
0
votes
2answers
25 views

$$\\|O(2n) - O(n)|=O(n)$$

I need to prove or contradict:$$\\|O(2n) - O(n)|=O(n)$$ I try: $$\\f(n)=1.5n\in O(2n),g(n)=0.25n\in O(n),h(n)>0\in O(n) : \\ |1.5n - 0.25n|=h(n)\\1.h(n)=1.25n \in O(n)\\ but: 2. h(n)=-1.25n \notin ...
2
votes
0answers
61 views

How to maximize speed of rest position approach of nonlinearly damped spring oscillator?

Inspired by comments to answer for this question: Suppose we have a system which is described by the equation $$\ddot x=-x+g(\dot x),$$ with initial conditions $x(0)=1$, $\dot x(0)=0$. If ...
0
votes
1answer
24 views

Is it possible to integrate this asymptotic expansion?

Suppose that some smooth function $f \in C^\infty\bigl(\mathbb R^n \times (0,+\infty)\bigr)$ possesses an asymptotic development $$ f(x,t) \sim t^{-\alpha} e^{ith(x)} \sum\limits_{k=0}^{+\infty} ...
3
votes
0answers
38 views

WKB and asymptotic behavior of second order differential equation

I want to study the large $x$ solution to a Riccati equation. After listening to the lectures on Mathematical Physics by Carl Bender, I have fallen in love with asymptotic analysis. But, by no means ...
0
votes
0answers
26 views

Stochastic big O notation

Let $||.||$ indicate the Euclidean norm. Let $\theta_0$ be a specific value of the parameter $\theta \in \Theta\subseteq \mathbb{R}^d$ and $G_n$ be a random vector-valued function $$ G_n : \Theta ...
2
votes
0answers
18 views

Asymptotic behaviour of oscillating integral

I'm interested in the big $x$ ($x \to \infty$) behaviour for the following integral $\int_{-\infty}^{\infty} \frac{dk}{\sqrt{k^2+1}} \frac{e^{-\sqrt{k^2+1}/2}}{1-e^{-\sqrt{k^2+1}}} e^{ikx}$ After a ...
0
votes
0answers
22 views

Relations between stochastic Big O-Notation, limsup and lim?

I have to solve a list of exercises on probability theory but I'm having several problems in understanding the following questions; could you help me? Thank you! Let $||.||$ indicate the Euclidean ...
0
votes
0answers
38 views

Meaning of theta notation in summation.

Just a simple question: What does the big theta notation mean in this equation? $$S(n,p) = \sum_i^ni^p=\Theta(n^{p+1})$$
1
vote
1answer
36 views

Prove the following $\Omega(n\cdot f(n)) = n\cdot \Omega(f(n))$

I want to prove the following by definition of asymptotic notation $$\Omega(n\cdot f(n)) = n\cdot \Omega(f(n))$$ Any suggestions?
5
votes
2answers
71 views

Asymptotic expansion of integral function

If we define $$F(x)=\int\limits_{2}^{\infty}\frac{x^t}{\ln(t)}dt$$ I'm interested in the asymptotic expasion of $F$ as $x$ approaches 1. I'm pretty sure this integral has no elementary ...
0
votes
1answer
34 views

Show that $f(n) = 2n^4 + 4n^2 + 5$ has a tight bound of $\Theta(n^4)$

What I have done so far (planning on showing lower and upper bound first): Lower bound: $$c_1n^4 \leq 2n^4 + 4n^2 + 5$$ Divide by $n^4$ $$c_1 \leq 2 + \frac{4}{n^2} + \frac{5}{n^4}$$ Take limit as ...
0
votes
0answers
20 views

Finding the Probability Limit and Asymptotic Distribution of Xbar-LogYbar

I'm kinda still new to Large Sample Theory and I have already attempted the question. Not sure if I did it right. Based on Kinchin , I know Xbar converges in probability to mu and Ybar converges in ...
1
vote
1answer
35 views

$\ln(f(n))\in \theta(\ln(g(n)))$ Its true that: $(g(n))^{f(n)}\in \theta((f(n)^{g(n)})$?

I want to prove the following: $\ln(f(n))\in \theta(\ln(g(n)))$ Its true that: $$(g(n))^{f(n)}\in \theta((f(n)^{g(n)})$$ How I can use $\ln$ function to prove it? prove by definition its ...
0
votes
1answer
81 views

$|f(n)-g(n)|\in \mathcal{O}(t(n)) $ And $f(n)+g(n)\in \Omega(t(n))$,Its true that $f(n)\in \Omega(t(n))$?

I want to prove the following by the definition $$|f(n)-g(n)|\in \mathcal{O}(t(n)) $$ $$f(n)+g(n)\in \Omega(t(n))$$ Its true that $f(n)\in \Omega(t(n))$? What I tried is just think about ...
1
vote
2answers
34 views

Describing asymptotic behaviour of a function

For question B! x^2+x+1/x^2 = 1+ [x+1/x^2] shouldnt the answer be asymptote at x=0 and y=1 ?? i dont understand the textbook solution