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
44 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
37 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 + ...
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
29 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
36 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
30 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
18 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
14 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
0answers
18 views

Asymptotic Equivalence

I've got this expression: $x^{3/4}-x^{4/3}$. I need to find the asymptotic equivalent as $x$ approaches $0$, expressing in the form: $Ax^p$ How do I solve this problem?
7
votes
1answer
268 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
84 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
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
49 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
28 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 ...
2
votes
2answers
105 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}$$
6
votes
1answer
115 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 ...
0
votes
0answers
21 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 ...
1
vote
1answer
31 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 ...
7
votes
1answer
194 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
0answers
25 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
0answers
22 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
0answers
31 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 ...
4
votes
3answers
109 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} ...
-1
votes
1answer
127 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
45 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
66 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
89 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
21 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 ...
6
votes
4answers
272 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
44 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
49 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
39 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
41 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|$. ...
0
votes
1answer
24 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
19 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
38 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
26 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
60 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 $$ ...
2
votes
2answers
89 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
18 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
77 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
27 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
53 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
28 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 ...
1
vote
2answers
56 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
0answers
22 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
43 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
30 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)). ...