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

learn more… | top users | synonyms (1)

4
votes
1answer
47 views

Examples of sub-exponential functions that aren't exponential functions when chained by a polynomial

Wikipedia talks about two groups of functions with asymptotic growth rates between polynomial and exponential – quasi-polynomial functions and sub-exponential functions. It only gives two ...
0
votes
0answers
50 views

Help inequality with $O(\cdot)$ and $\Omega(\cdot)$

Suppose,$$f(T)\le O\left(\sqrt{\dfrac{\log( T/\delta)}{T}}\right).$$ If we let $\delta=\dfrac{1}{n^2}$ and $T\ge\Omega\left(n^2\log n\right)$, then: $$f(T)\le \dfrac{1}{n}.$$ Can anyone ...
0
votes
2answers
55 views

Sum of independent Bernoulli variables with parameter p which is also a random variable

I've read all the questions related to this, but I couldn't find an answer. We have n independent Bernoulli variables $X_i \in Be(p_i)$ where all the $p_i$ have the same distribution, let's say ...
1
vote
1answer
54 views

Meaning of $\sim$?

I often read $f(x) \sim g(x)$ and I wonder what the Standard Interpretation of this $\sim$ is. It seems to mean something like asymptotically equally distributed, something like $f(x)=g(x)(1+o(1))$. ...
3
votes
1answer
89 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 ...
2
votes
1answer
43 views

How can we show that if $f(n) = O(n^2)$, then $ f(n) = O(n^3)$

I'm looking at the 'positive constants' definition, but just not seeing how to go from here to there.
1
vote
1answer
22 views

Using Stirling's approximiation to show that $(\log(\log n))!$ is $O(n^k)$

I am trying to show the following: Prove, using Stirling's approximiation, that $(\log(\log n))!$ is $O(n^k)$ for some positive constant $k$. Stirling's approximation is $$n!=\sqrt{2\pi ...
2
votes
1answer
30 views

Asymptotic approximation for the r-associated Stirling numbers of the second kind

It is well know that for fixed $k$ the asymptotic approximation for the Stirling numbers of the second kind is given by $\frac{k^n}{k!}$. Does such simple asymptotic expression also exist for the ...
1
vote
0answers
29 views

Asymptotic analysis of certain multiple integration of power functions

Let $t_1,\ldots,t_m>0$, and $m\ge 4$ be an even integer. Consider the function: $$ f(a,b;\mathbf{t})=\int_0^{t_1}\ldots\int_0^{t_m} |x_1-x_m|^a |x_2-x_1|^b |x_3-x_2|^a |x_4-x_3|^b \ldots ...
0
votes
0answers
45 views

Biggest common sub-string search asymptotics

What is the function of Big-O in case where we use brute-force on two strings to find the biggest common sub-string. Please can you explain the underlying logic to the resulting formula corresponding ...
0
votes
0answers
26 views

Theoretical question of physical analogies to different O(f(x)) based characteristics of algoritms

I want to better understand the following concepts: "n!", "e^n". I.e. what is the physical analogy of the functions at the bottom of the message. F.ex. for the "n^a" and "log a x" where a equals to ...
30
votes
0answers
685 views

On the number of complete and gap-free compositions

This is a longish post about something that has been haunting me for a while about a kind of restricted composition, namely gap-free and complete compositions. First, I will define the terms that are ...
11
votes
1answer
127 views

Asymptotic behavior of $|f'(x)|^n e^{-f(x)}$

Let $f$ be a strictly convex function on $\mathbb R$, $f'' \geq C > 0$. Let $n$ be a positive integer. What can we say about the growth rate of $|f'(x)|^n e^{-f(x)}$ as $x\rightarrow \infty$? Must ...
0
votes
1answer
14 views

Does this function go to zero faster than the norm of its argument?

Assume $f:\mathbb R^2\to\mathbb R$ is such that for all $\varepsilon>0$ exists $\delta>0$ such that, whenever $||x||<\delta$, also $||f(x)||<\varepsilon^2$. Can we see that $f$ is ...
1
vote
1answer
48 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: ...
0
votes
1answer
35 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 ...
0
votes
0answers
19 views

Solving recurrence relation with $c=\Theta(\log(\log(n)))$

The master theorem in recurrence relations, i encounter with difficulty in solving problems, which have $c=\Theta $ $($of something$)$ or when it has $\log(n)$ or its variants instead of a simple ...
7
votes
3answers
477 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 ...
7
votes
2answers
66 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 ...
0
votes
2answers
434 views

merge sort vs insertion sort time complexity

How do I solve exercise 1.2-2 from Introduction to Algorithms 3rd Edition, Author: Thomas H. Cormen Would I need to set both sides equal to each other and solve for n?
9
votes
3answers
542 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} ...
1
vote
3answers
112 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
22 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) = ...
1
vote
2answers
27 views

Asymptotic notation: A function is Θ-Notation

H. Cormen, Exercise 3.1-2 The following statement is true? If yes, prove that it is true. $$ (n+a)^b = Θ(n^b)\\ a, b \in R\\ b>0 $$ I tried to expand $(n+a)^b$ using the Binomial theorem, but ...
0
votes
1answer
31 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 ...
0
votes
1answer
43 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
36 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
267 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 ...
1
vote
1answer
378 views

Asymptotic Matching for boundary layer problem

The question asks to find a global approximation to the leading order of $\epsilon$. $\epsilon y'' + xy' + \epsilon y =0$, with boundary conditions $y(0)=1,y(1)=-1$. I assumed it's a boundary layer ...
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
104 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
113 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
182 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
24 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
21 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
123 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 ...