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
947 views

The Asymptotic Expansion of The Exponential Integral

I was reading R. Wong's book on Asymptotic Approximations of Integrals, and I'm having problems with the derivation of the asymptotic expansion of the exponential integral which he defined as follows: ...
-1
votes
1answer
51 views

asymptotic notations and their running time [closed]

I know that for $f(x) = O(g(x))$ running time $T(n) = O(n^3)$ $f(x) = \Omega(g(x))$ running time $T(n) = \Omega(n^2)$ but what is the $T(n)$ for $f(x) = Θ(g(x))$ ? Also tell me running time for ...
9
votes
3answers
2k views

Can asymptotes be curved?

When I was first introduced to the idea of an asymptote, I was taught about horizontal asymptotes (of form $y=a$) and vertical ones ( of form $x=b$). I was then shown oblique asymptotes-- slanted ...
8
votes
2answers
118 views

Asymptotically, how many random students do I have to mark before I've marked two consecutive students

Background The motivtion for this question comes from observations made by a colleague while he was marking homework and recording the marks this year. His procedure for recording the marks is as ...
11
votes
3answers
717 views

Equivalence to the prime number theorem

I was just reading this question and answer: How will this equation imply PNT and it raised a whole new question: Given that $\sum_{n\le x} \Lambda(n)=x+o(x)$, prove that $$\sum_{n\le x} \frac{...
1
vote
3answers
122 views

A system of $n$ equations , how does it behave for growing $n$?

I read about the system of $n$ equations in the link below. I wonder how it behaves for growing $n$. Does it converge ? http://math.eretrandre.org/tetrationforum/showthread.php?tid=889 Here it is ...
0
votes
1answer
52 views

Change of variables in function $T(n)$.

I've been given this recurrence to solve: $T(n) = T(\sqrt n) + \theta(lglgn)$ And I'm told that the way to solve it is to let $m = lgn$, so that the recurrence can be rewritten as follows: $S(m) = ...
0
votes
1answer
64 views

Master Theorem , Polynomial, recurrences

Going through Master's theorem for recurrences but I am seriously confused as what it means when we say that function f(n) is polynomially greater than function g(n) (Case 3) and how can one check ...
1
vote
0answers
41 views

Asymptotic behavior of oscillatory Hilbert transform

Does anyone know what is the leading term in the asymptotics of $$ P.V. \int\limits_{ -\infty }^{ +\infty } \frac{e^{i \lambda x^3 } f( x ) dx }{ x }, $$ as $ \lambda \to +\infty $? Assume $ f \in C_{...
1
vote
2answers
39 views

math rules when having 2 variables in Big-O

I came across the following in some lecture notes: O(log n) + O(log m) = O(log n + log m ) = O(log (m + n)) that last step to ...
0
votes
0answers
106 views

Growth rate of integral

My apologies, I have no idea how to make the title more specific without putting the whole question in there. On p. 60 of Montgomery and Vaughan they state \begin{equation} 2\int_e ^x \frac{1 + \log \...
2
votes
1answer
53 views

Extrema of the Ratio of Consecutive Primes

Let $p_i$ denote the $i$th prime number. We know that $\frac{p_{n+1}}{p_n}\rightarrow 1$ as $n\rightarrow\infty$. Therefore, if we pick some real number $c>1$, there should be some positive integer ...
0
votes
1answer
31 views

Asymptotic expansion of $z^{-x}$

Consider the function $z\mapsto z^{-x}$ for $x>1$ (real) and $z$ in the cut complex plane $\mathbb C\backslash\{z\leq 0, \text{ real}\}$. Does this function have an asymptotic expansion of the form ...
0
votes
1answer
38 views

First Order Approximation Taylor Series

I have the taylor series $f(z)=f(x_0)+(x-x_0)f'(z)+1/2(x-x_0)^2f''(z) ...$ and I am told that "As a first order approximation," $x-x_0$ ~ $\frac{f(x)-f(x_0)}{f'(x_0)}$ assuming $f'(x_0) \neq 0$ I ...
9
votes
1answer
777 views

How to compute the asymptotic growth of $\binom{n}{\log n}$?

I'm interested with tight bounds for: $$f(n)={n\choose{\log{n}}}$$ It sounds like it's something simple, but I can't get a nice expression I can use. Any ideas on how to do this?
1
vote
0answers
91 views

Does the index of a curve determine the asymptotic behaviour of certain vector fields?

There are a collection $C$ of charges in $\mathbb{R}^2$ which cause an electric vector field $V$ to form. Each charge's contribution to $V$ follows the inverse-square law. Let $\gamma$ be a curve ...
0
votes
1answer
51 views

Big-O Analysis: Max Bounded by the Sum

I have been asked to show that: $$ \mathcal{O}(Max\{ f(n), g(n) \}) = \mathcal{O}(f(n) + g(n)) $$ I have seen explanations of similar problems, but this is the first time I have encountered the ...
0
votes
0answers
70 views

Asymptotic complexity of $\sum_{k=1}^m \binom{2^m}{2^k} \binom{2^k}{2^{k-1}}$

I'm trying to examine the asymptotic complexity of $$f(m) = \sum_{k=1}^m \binom{2^m}{2^k} \binom{2^k}{2^{k-1}}$$ Question: How do you prove or disprove $f(m) \in \mathcal{O}(2^{2^m})$? Bonus ...
2
votes
2answers
158 views

Calculate limit with factorial

I need to find the limit of this function..I thought about L'hôpital's rule, but can't seem to derive them both.. $$\lim_{n\rightarrow\infty} \frac{(2n)!}{(n!)^2}$$
1
vote
1answer
53 views

How on earth will anyone prove $n^3-3n^2+n-1=Θ(n^3)$

I know its homework question.Sorry for that.But i was solving all problems of Skiena and chapter and got stuck to this problem of 2nd chapter 2.10. Its easy to prove $n^3-3n^2+n-1=O(n^3)$ because $n^...
8
votes
1answer
307 views

First-term approximation for singular perturbation of ODE (with two turning points)

I'm reading "Introduction to Perturbation Methods" by Mark Holmes, and I came across an exercise that I don't know how to approach. As I decided to independently read this book, I have no friends/...
1
vote
1answer
44 views

Help understanding this approximation

In a paper that I'm reading, the authors write:- $$N_e \approx \frac{3}{4} (e^{-y}+y)-1.04. \tag{4.31}$$ Now, an analytic approximation can be obtained by using the expansion with respect ...
5
votes
3answers
725 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
1answer
474 views

Asymptotic value of Fibonacci numbers

It is well known that $F_n\sim\frac{\phi^n}{\sqrt{5}}$, where $\phi=\frac{1+\sqrt{5}}{2}$. Does someone know a better estimate? With proof please. I'm trying to calculate the following limit: Let $...
0
votes
1answer
49 views

Can we say that $ 2^\frac{n}{\log(n)} \sim 2^\frac{\log(n)}{\log(\log(n))}$?

Can we assert and proove that : $$ 2^\frac{n}{\log(n)} \sim 2^\frac{\log(n)}{\log(\log(n))}$$ And What inequality relating two parts can be proved ?
1
vote
1answer
123 views

Numerical Analysis - Richardson Extrapolation

Question: Suppose that N(h) is an approximation to $M$ for every $h > 0$ and that $M = N(h) + K_1 h + K_2 h^2 + K_3 h^3 +\cdots$, for some constants $K_1, K_2, K_3,\cdots$. Use the values $N(h), N( ...
3
votes
1answer
153 views

Asymptotic behavior of a sequence of integrals

I am interested in the asymptotic behavior of sequences $(I_n)$ and $(J_n)$ as $n \rightarrow \infty$, where $$I_n = \int_{1}^{\infty}\frac{e^{-nx^2}}{x^2}\, dx,$$ and $$J_n = \int_{0}^{\infty}\...
1
vote
0answers
29 views

asymptotics of the solution of an integral equation

Suppose we are given the integral equation $$ u(x;a) =v(x)+\int_0^a K(x,y)\,u(y;a)\,dy, $$ where $K(x,y)$ and $v(x)$ are known functions, and $a>0$ is a constant. What I am interested in is the ...
10
votes
4answers
513 views

What is the difference between analytic combinatorics and the theory of combinatorial species?

Yesterday I asked the question Why should a combinatorialist know category theory?, where Chris Taylor suggested me to have a look at combinatorial species. I had heard the term before but I haven't ...
0
votes
2answers
161 views

Complexity of $T(n) = 2T(n/2) + n$

How can I prove that $T(n) = 2T(n/2) + n$ is $\mathcal{O}(n \, \log{n})$ without master theorem , if $T(1)=\mathcal{O}(1)$? How can I continue from here? $T(n) = 2T(n/2) + n,$$T(n) = 4T(n/4) + 2n,$$...
4
votes
0answers
60 views

A general question of asymptotics

I am very desperately longing to know if there is a explicit relationship between $$F(n)=f(1)+f(2)+...+f(n)$$ and $$G(x)=\sum_{k=1}^{\infty}f(k)x^k$$ Assuming we can let $f$ be a sufficiently well ...
1
vote
1answer
132 views

Question about Big O Notation

I don't seem to understand big-O notation very well. If someone would explain it to me as well as explain how this problem would work Let f(n) = (3$^n$$^+$$^1$ - 3)/2. For each of the following ...
0
votes
2answers
73 views

Big O notation $a*n + b = O(n^2)$

According to the book "Introduction to Algorithms" a function that has the following form$f(n)=an+b$belong to $O(n^2)$ , and that this can be easily proven if we set$c = a +|b|$ But I don't get it, it ...
1
vote
1answer
15 views

relation between $|o(f)-g|$ and $|f-g|$

This question is similar to the one asked some hours ago. I have given three functions $f,g,h$ where $h(n)=o(f(n))$ and I know that $|f-g|<d<1$. Now I'd like to find an Expression for $|h-g|$. ...
0
votes
1answer
156 views

What is the time complexity of an $O((\ln n)^{\ln n})$ algorithm?

How can the time complexity of an $O((\ln n)^{\ln n})$ algorithm be simplified and compared to some other time complexities?
0
votes
1answer
26 views

$O(f)-g = O(f-g)$: asymptotics of difference of functions

I have given three functions $f$, $g$, $h$ where it might be relevant that all these functions are bounded from above by $1$. I know that $$|f-g|=d$$ where $d$ may depend on $n$ and I know that $$h(...
0
votes
1answer
56 views

Why $\lim_{n\to\infty}(1-\frac{\sigma^2\xi^2}{2n}+o(\frac1n))^n= e^{-\frac{\sigma^2\xi^2}{2}}$

Why is $\lim\limits_{n\to\infty}\displaystyle\Big(1-\frac{\sigma^2\xi^2}{2n}+o(\frac1n)\Big)^n=\large e^{-\frac{\sigma^2\xi^2}{2}}$ ? Why has $o(\frac{1}{n})$ no effect on the term ? Can I also ...
0
votes
1answer
94 views

Sum of bounded in probability random variables

I'm self-studying probabilistic order notation, and I wanted to show some properties to get used to it. But now I'm having trouble showing that the sum of two random variables that are bounded in ...
2
votes
2answers
100 views

Properties of Big $\mathcal{O}$

I have seen in a paper that, if $A=\mathcal{O}(p^2)$ and $B=\mathcal{O}(p)$ then, how can we say that, $A^{-1/2}B$ is diverging? The way I thought is, if $A = \mathcal{O}(p^2)$, then $A^{-1/2}$ = $...
0
votes
1answer
21 views

Asymptotics of two functions

Is $$O(1-cf(n))=O(1-f(n))$$ for any constant $c$ and any function $f$? I am afraid not. Could you tell me how to get from $$1-cf(n)$$ to $$1-f(n)?$$ Anything I can think of is $$1-cf(n)=c(1-f(n))+1-c=...
3
votes
1answer
104 views

Asymptotic of a sum evaluation as $ x \to \infty $

Let be the sum $$ \sum_{n\le x}[x/n]=g(x) $$ where $ [x] $ means floor function. My best try for asymptotic is $ g(x) \sim x\log (x)+\gamma x +1$ where I have used the asymptotic $ [x] \sim x $ ...
0
votes
1answer
34 views

What is the value of $p(z) \log(z)$ around a contour centered on the origin?

Given a polynomial $p(z)$, and a rectangle with vertices $2+iM, -3+iM, -3-iM, 2-iM$ what is the value of $f(z) = p(z) \log(z)$ around the contour? Or equivalently the change in argument? In ...
3
votes
1answer
76 views

What is the proper way to handle the limit with little-$o$?

I was hoping to show that $$\left(1-\frac{x}{n}+o\left(\frac{2x}{n}\right)\right)^n \xrightarrow{n\to\infty} e^{-x}$$ which would be just fine without the little-$o$. Trying binomial formula: $$\...
1
vote
2answers
66 views

Question on asymptotes

Consider a function $f: \mathbb{R} \to \mathbb{R}$ that has an asymptote at $- \infty$ of the type $y=\lambda x + \beta$. According to trigonometry $\lambda=\tan{\theta}$ for a very small value of x ...
2
votes
1answer
147 views

Time complexity of random algorithm

I was wondering how to perform the complexity analysis of the following random algorithm. The answer are: $\Omega(n)$, $O(n²)$, and $\Theta(n)$. At first I thought to perform the analysis by saying ...
1
vote
2answers
42 views

$f(n) \in o(g(n))$ and $g(n) \in o(f(n))$

Could you help me with the following problem? Can there be two non-negative functions $f(n)$ and $g(n)$ such that $f(n) \in o(g(n))$ and $g(n) \in o(f(n))$? Just to make it clear, here is a ...
3
votes
2answers
66 views

if $f(x) \sim g(x)$ is $ \sum f(k) \sim \sum g(k)$

if $f(x) \sim g(x)$ as $x \to \infty$ then is $\sum_{k=1}^N f(k) \sim \sum_{k=1}^N g(k)$ as $N \to \infty$? Intuitively, i should think so because as $k$ gets larger $f$ and $g$ get closer so it ...
-1
votes
1answer
85 views

Understanding Recurrence Relation

as i ask question and answered by some Clever people at this topic: Recurrence Relation Solving Problem i try to learn new thing with new question very similar to get familiar with recurrence ...
1
vote
1answer
195 views

Rate of convergence of an exponential function

If I have a function $$f = \exp(\sqrt{n} \cdot \frac{\sqrt{\log{n}}}{\sqrt{n}-\sqrt{\log n}}),$$ I can notice, that $$\lim_{n \to \infty} f = \infty,$$ but also I can notice that it goes very slowly ...
3
votes
1answer
64 views

Prove $\lim_{n \to \infty} \frac{\Gamma(n+1/2)}{\Gamma(n)~n^{1/2}}=1$

Prove $$\lim_{x \to \infty} \frac{\Gamma(x+1/2)}{\Gamma(x)~x^{1/2}}=1.$$ I got this problem from Probability and Statistics by Degroot & Schervish. There is a hint to use Stirling's formula ...