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

learn more… | top users | synonyms (1)

1
vote
0answers
24 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 ...
1
vote
2answers
31 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
38 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 ...
1
vote
0answers
43 views

Sums of Power Law random variables

Suppose $F$ be a pareto distribution with scale parameter $x_m$ and shape parameter $\alpha$. Assume $X_1, X_2 , ..., X_n$ are iid random variables drawn from $F$. Let $S_n(k) = X_1 ^k + X_2 ^k + ...
0
votes
1answer
20 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 ...
2
votes
1answer
35 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
17 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 ...
0
votes
1answer
27 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
50 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 ...
0
votes
1answer
31 views

Is $f(n) + O(f(n)) = \theta(f(n))$?

I've been asked to show whether this is always, never or sometimes true. I think I understand that in this situation, $O(f(n))$ can be treated as a macro for some function $g(n)$. So if the equation ...
6
votes
1answer
124 views

How to solve the non-linear differential equation $y''=x-y^2$?

$y''(x)=x-y^2(x)$ I'm particularly interested in solutions when $x>0$. I've performed asymptotic analysis and reached the conclusion that solutions must behave as $\pm\sqrt{x}$ when $x\rightarrow ...
-1
votes
0answers
22 views

Max Function Notation [duplicate]

I've been asked whether the following is always, never or sometimes true: $f(n) + g(n) = \theta(\max(f(n), g(n)))$ I understand the definition of theta notation, but I'm not sure how to read the ...
2
votes
2answers
111 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
33 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 ...
0
votes
0answers
26 views

Finding a leading order approximation for a system of ODE (multiple scales)

I need to find the leading order approximation which is valid for times $t=ord(\frac{1}{\epsilon} ) $ as $\epsilon \to 0$ to the solution $x(t,\epsilon)$ and $y(t,\epsilon)$ satisfying: ...
0
votes
1answer
32 views

Determine the realtions ($\mathcal{O}$,$\Theta$,$\Omega$ ) between $f(n) = \ln(n^{c} + n^{d})$ and $g(n)=\ln(n^{a} + n^{b})$

I am trying to determine the realtions ($\mathcal{O} $,$\Theta$,$\Omega$ ) between : $$f(n) = \ln(n^{c} + n^{d})$$ $$g(n)=\ln(n^{a} + n^{b})$$ Note: $a,b,c,d>0$ I need some advice how to use the ...
1
vote
3answers
114 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
51 views

Upper bound for the sum $ \sum_{k=1}^N \frac{1}{\varphi(k)}$

Is there an upper bound for the sum $$ \sum_{k=1}^N \frac{1}{\varphi^{\alpha}(k)} $$ where $\varphi(n)$ is the Euler totient function and $\alpha\geq 1$ a real constant? In particular, I'm interested ...
1
vote
0answers
32 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 ...
-1
votes
1answer
153 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
47 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 ?
3
votes
1answer
99 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 = ...
1
vote
0answers
22 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 ...
0
votes
2answers
45 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) + ...
4
votes
0answers
51 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 ...
7
votes
1answer
208 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 ...
0
votes
2answers
43 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
12 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|$. ...
1
vote
0answers
86 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
35 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
20 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 ...
0
votes
1answer
44 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
39 views

Why does for $f(n)\sim n^{-1/3}$ we have $g(n) \equiv [f(n)]^2 = O(n^{-2/3}) = o(n^{-1/2})$ as $n\to\infty$ for $n\geq 1$?

Using the definition we have $$n^{2/3}g(n)\leq C<+\infty$$ On the other hand $$\lim_{n\to\infty}n^{1/2}g(n)=0$$
0
votes
1answer
31 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 ...
0
votes
0answers
62 views

Recurrence equation analysis of the form T(x) = t + max{T(…) + …}

I want to find the worst-case running time of an algorithm I came up with, which follows the following recurrence equation: The worst-case running time is $\Theta(n^2) + T(n, 2, n)$, where $$ ...
0
votes
1answer
19 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 ...
3
votes
1answer
80 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
28 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
54 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: ...
0
votes
1answer
29 views

Big O notation for complex-valued functions of a real variable

Let $f,g:\mathbb R\to\mathbb C$. Is there a standard notion of $f = O(g)$? If I had to take a stab at a definition, I'd try something like $f = O(g)$ provided where exists $M>0$ and ...
2
votes
0answers
24 views

Asymptotics of the differences between successive zeta zeros

Does anyone know what the asymptotic of the differences between successive zeta zeros is? Update It appears that $\zeta(n)$ is not a bad asymptotic, when the data range is stretched: ...
2
votes
1answer
49 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 ...
0
votes
1answer
58 views

f(n)=theta(f(n/2)). Prove or disprove

I am trying to prove that the statement f(n)=theta(f(n/2)) is true. This is what I have so far. I am not sure it is correct. Assume f(n)=Theta(f(n/2)). Then f(n)=O(f(n/2)) and f(n)=Omega(f(n/2)). ...
1
vote
2answers
57 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 ...
1
vote
2answers
34 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 ...
2
votes
2answers
61 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 ...
0
votes
1answer
67 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
52 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 ...
4
votes
1answer
110 views

Asymptotic expansion of $\int\limits_0^{\pi / 2} {e^{ix\cos t}}dt$

Using the method of stationary phase, I was able to obtain the first term of the asymptotic expansion of the following integral, as $x \rightarrow \infty$: $$\int\limits_0^{\pi / 2} {e^{ix\cos t}}dt ...
3
votes
1answer
49 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 ...