Questions involving asymptotic analysis, including growth of functions, Big-O notation, Big-Omega and Big-Theta notations.
10
votes
8answers
233 views
Limit of $\frac{\log(n!)}{n\log(n)}$ as $n\to\infty$.
I can't seem to find a good way to solve this.
I tried using L'Hopitals, but the derivative of $\log(n!)$ is really ugly. I know that the answer is 1, but I do not know why the answer is one.
Any ...
2
votes
1answer
30 views
How to interpret little-o notation in an exponent.
The definition for the little-o notation that I am using is the following: We write $f(n)=o(g(n))$ if $|f(n)|\leq c_ng(n)$, where $(c_n)$ is a sequence such that $c_n\to 0$ as $n\to\infty$.
With this ...
1
vote
1answer
74 views
asymptotic behavior of the real part of the Riemann zeta function for $0<\sigma<1$
consider the zeta function $\zeta(\sigma+it)$ for $\sigma>1$ :
$$\zeta(\sigma+it)=\sum_{n=1}^{\infty}\frac{1}{n^{\sigma+it}}$$
And:
$$\zeta(\sigma-it)=\sum_{n=1}^{\infty}\frac{1}{n^{\sigma-it}}$$
...
0
votes
1answer
36 views
Solve the recurrence $T(n) = T(\log_2 n) + 13n$
I have the following recurrence relation $$T(n) = T(\log_2 n) + 13n.$$
I believe in order to solve the equation I need to determine the height of the tree.
$$T(n) \to T(\log_2 n) \to ...
2
votes
2answers
45 views
Prove the following: Product of Roots
$1^{(1/1)} \cdot 2^{(1/2)} \cdot 3^{(1/3)} \cdot 4^{(1/4)} \cdot 5^{(1/5)} $.... diverges
well I don't really know if it does but my gut tells me it does:
I can take the log of this product
to ...
10
votes
2answers
178 views
Asymptotics of the sum of squares of binomial coefficients
We are trying to estimate the cardinality $K(n,p)$ of so-called Kuratowski monoid with $p$ positive and $n$ negative linearly ordered idempotent generators. In particular, we are interesting in the ...
1
vote
1answer
31 views
Integral of smooth function
Another prelim problem:
Suppose that $f(x,y)$ is a smooth function defined on $\mathbf{R}^2$. Prove that
$$
\int_{x^2+4y^2\leq r^2}f(x,y)\,dx\,dy = ar^2+br^4+O(r^5)
$$
Express $a$, and $b$ in terms ...
3
votes
1answer
47 views
Subtraction of Big $O$'s
So we were asked to prove something in class, but I can't understand the following expression:
What is $O(n^2)-O(n^2)$?
I understand big O notation, but what I don't understand is the ...
1
vote
1answer
49 views
Integral representation of a function
Here is another Prelim problem from Advanced Calculus.
For $t>0$ and $D>0$ define $g(x,t)$ by
$$
g(x,t)=\frac{1}{\sqrt{Dt}}\exp{\frac{-x^2}{4Dt}}
$$
Now, for $f:\mathbf{R}\to\mathbf{R}$ being ...
0
votes
1answer
26 views
Big O Notation in two equations
If $a = b + O (c)$, $d = e + O (f)$ and $b > e$, can we say that $a > d$? I proceeded by substracting the two equations. I think I have not done any thing wrong. It gives $a-d=b-e + O(c-f)$ and ...
0
votes
1answer
17 views
Mixing asymptotic notations
I have a function $f(x) = g(x) - h(x)$ and I know that $g(x)=\Omega(\hat g(x))$ and $h(x)=O(\hat h(x))$. Is it well-defined to express this in asymptotic notation, as $f(x) = \Omega(\hat g(x))-O(\hat ...
2
votes
0answers
35 views
How prove this $\frac{|x-z|}{|x-y|}=1+\frac{1}{|x|}\hat{x}\cdot(y-z)+O(1/|x|^2)$
prove that
$$\dfrac{|x-z|}{|x-y|}=1+\dfrac{1}{|x|}\hat{x}\cdot(y-z)+O(1/|x|^2)$$
for $|x|\longrightarrow \infty$
where
$$\hat{x}=\dfrac{x}{|x|}$$
This problem from book,following is my idea:
...
2
votes
1answer
76 views
How to prove that $\lim_{x\to \infty} x/2^x = 0$
I need to prove that $\lim_{x\to \infty} x/2^x = 0$
I'm not sure I did it right:
I applied L'ôpital's rule and obtainded: $\lim_{x\to \infty} \dfrac{1}{2^x\ln2}$
and this is equal to ...
1
vote
0answers
36 views
What is the relationship between singularities for complex times and high frequency asymptotics?
As said in a paper I am reading on p 2677 in the text directly above FIG3, this should be a standard result about Fourier transforms of analytic functions. In the paper the authors use these methodes ...
1
vote
1answer
20 views
How do we determine as to how long we should sum an asymptotic series of a function to get the answer correct up to a particular precision?
As an example, consider the asymptotic expansion for polygamma function . What should be the min value of 'k' in the equation to get the answer correct upto a particular precision, say pth. Is there ...
3
votes
1answer
137 views
The geometric mean of primes less than or equal to $x$
I want to show that the limit of the geometric mean of primes less than or equal to $x$ is $e$ as $x \to \infty$. Is this correct?
Using the product law of logarithms we have
$$\ln \prod\limits_{p ...
6
votes
0answers
59 views
Asymptotic Expansion of an Oscillating Integral
Let $g(x):\mathbb{R}_{\geq0}\rightarrow\mathbb{R}$ be real analytic s.t. $g(0)\neq 0$ and $g(x)=O(x^{-2})$ as $x\rightarrow\infty$.
What is the leading order in $\lambda$ as $\lambda\rightarrow 0$ of ...
1
vote
3answers
42 views
Big-Theta Notation. Is this theorem true?
Is the following sentence true assuming that $f$ and $g$ are differentiable and their derivatives are continous? I'd say yes, but don't know how to show it.
$$g(x) \in \Theta(f(x)) \iff \frac{d}{dx} ...
4
votes
2answers
87 views
Using sum of logarithms of primes to prove the number of primes up to $n$ is $O(n/\log n)$
I need to show that the number of primes up to $n$ (i.e. $\pi(n)$) is $O(n/\log n)$.
In the previous exercise of this question I proved that ${\displaystyle \sum_{i=1}^{\pi(n)}\log p_{i}} \leq Cn$ for ...
0
votes
1answer
20 views
Master Method and use cases
$T(n)=T(n-2)+n^{2}$ and $T(n)=4T(n-2)+n^{2}$
Master method to solve these two equations? I know I can use the other cases where $a$ and $b > 0$ but since $T(n-2)$ do I assume $b$ is $1$?
3
votes
3answers
246 views
The order of $\sqrt{\epsilon(1-\epsilon)}$ and $4\pi^2\epsilon$ as $\epsilon \rightarrow 0$?
I was reading on the big O/little O notation etc. and I understand the definitions, but how exactly would I use it to find the order of an expression/function?
I am asked to determine the order of ...
1
vote
4answers
69 views
How to prove that $\lim_{n\to \infty} (n^k/2^n) = 0$?
I'm having a hard time trying to prove this statement.
$\lim_{n\to \infty} (n^k/2^n) = 0$
k is a positive number.
Please, help me.
Thanks in advance.
0
votes
1answer
21 views
prove the statement (big O notation)
Prove the following statements:
$2^n$ is $O(n!)$, and
$n!$ is not $O(2^n)$
not sure where to start with these two... thanks
0
votes
0answers
18 views
Complexity of index calculus method
I read somewhere that complexity of index calculus method which calculates discrete logarithm over $Z_p^*$ is
$O\left(e^{(1 + o(1))(\sqrt{ln(p)\times ln(ln(p))}\;)}\right)$.
My question is, why ...
1
vote
1answer
47 views
How to prove that $n^k = O(2^n)$
I'm having issues trying to prove this.
The Big Oh definition is: f(n) = O(g(n)) if exists a real constant $c > 0$ and $n_0 \in \Bbb N $ in such a way that for all $n \ge n_0$ we have f(n) $\le$ ...
2
votes
1answer
37 views
Proof of asymptotic expansion of binomial coefficient
here's the problem I'm currently stuck on:
Prove that (for $k$ fixed):
$$\binom{N}{k}=\frac{N^{k}}{k!}+O(N^{k-1})$$
I know that:
$$\binom{N}{k}\le\frac{N^{k}}{k!}$$
But I'm not sure how to ...
2
votes
3answers
122 views
Studying $ u_{n}=\frac{1}{n!}\int_0^1 (\arcsin x)^n \mathrm dx $
I would like to find a simple equivalent of:
$$ u_{n}=\frac{1}{n!}\int_0^1 (\arcsin x)^n \mathrm dx $$
We have:
$$ 0\leq u_{n}\leq \frac{1}{n!}\left(\frac{\pi}{2}\right)^n \rightarrow0$$
So $$ ...
14
votes
2answers
470 views
Asymptotics of sum of binomials
How can you compute the asymptotics of
$$S=n + m - \sum_{k=1}^{n} k^{k-1} \binom{n}{k} \frac{(n-k)^{n+m-k}}{n^{n+m-1}}\;?$$
We have that $n \geq m$ and $n,m \geq 1$.
A simple application of ...
1
vote
2answers
65 views
$\cot(x)\,$ in the large $x$ limit?
I couldn't find asymptotic forms of trigonometric functions in any Math Table.
In particular, I am trying to find $\;\cot(a x)\;$ in large $x$ limit.
thanks,
8
votes
2answers
129 views
Estimate $\sum_{k=1}^{n} k^{k-1} \binom{n}{k} (n-k)^{n+1-k}$
I'm interested in estimating
$$X_n=\sum_{k=1}^{n} \binom{n}{k} k^{k-1} (n-k)^{n+1-k}$$
up to and including terms of order $n^n$; that is, I want $f_n$ in
$X_n=f_n+o\left(n^n\right)$.
...
2
votes
1answer
70 views
What is the name for a series that uses exponential functions of a variable, rather than powers of that variable, to approximate a function?
Consider the function $\text{sech}(\pi \frac{x}{2})$ and suppose that we wish to find an approximation for this function at large $x$. One route seems to be to write
$$ \text{sech}(\pi \frac{x}{2}) = ...
2
votes
2answers
27 views
Nesting of different Asymptotic operators
Is it possible to nest big-oh notation with omega-notation? I came across this here, while doing calculations on an exercise:
$$
f(x) \in O(\Omega(\log x))
$$
I'm really unsure on how to properly ...
1
vote
1answer
48 views
Can Cauchy theorem be applied to $\log{(z)}e^{ixz}$?
I'm reading about asymptotic analysis on the integral $I(x)=\int_0^1{\ln{t}e^{ixt}}dt$. The book tells me that I can use Cauchy theorem to deform the contour into a rectangular contour:0->iT, ...
3
votes
1answer
107 views
Is $\sum_{k=1}^{n} k^{k-1} (n-k)^{2n-k} \binom{n}{k} \sim\frac{n^{2n}}{2\pi} $?
How can you compute the asymptotics of
$$T=\sum_{k=1}^{n} k^{k-1} (n-k)^{2n-k} \binom{n}{k}\;?$$
This is related to Asymptotics of sum of binomials .
I attempted to simply use Stirling's ...
5
votes
1answer
67 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
2answers
43 views
Prove asymptotic bound?
Prove:
$$n^b = \mathcal{o}(a^n)$$
for and constants $b$ and $a$, where $a > 1$. The book states that:
$$\lim_{ n \rightarrow \infty} \frac{n^b}{a^n} = 0$$
The book doesn't prove the limit ...
11
votes
3answers
217 views
Order of the smallest group containing all groups of order $n$ as subgroups.
Let $n\in \Bbb N$ be fixed and $m\in \Bbb N$ be the least number such that there exists a group of order $m$ in which all groups of order $n$ can be (isomorphically) embedded.
Can we deduce $n!=m$?
0
votes
1answer
59 views
Solving a recurrence realtion using backward substitution.
So I've been trying my best to do this, and I have made some good progress, I just need to know if what I have done is correct and if not, what the hell am I doing wrong? :P
I start off with this ...
0
votes
1answer
84 views
Solving Recurrence Relation with Forward Substitution
I've found myself quite stuck on this recurrence relation. I've been given it to solve, via forward substitution and verify using induction. I start out with
$$
T(n) = 4T(n/3)
$$
For all $n > 1$ ...
1
vote
1answer
22 views
Dynamic Programming Trouble, Optimizing time
A robot goes from terminal to terminal collecting bolts. The robot needs to collect at least $m$ bolts and there are $n$ terminals. Terminal $i$ gives the robot a certain number of bolts denoted by ...
1
vote
0answers
101 views
Using the gamma function as an upper and lower bound to the logarithm of a factorial function.
I am trying to find an upper and lower bound for the following function:
$$f(x) = \ln(\lfloor\frac{x}{b_1}\rfloor!) - \ln(\lfloor\frac{x}{b_2}\rfloor!) - \ln(\lfloor\frac{x}{b_3}\rfloor!)$$
where
...
17
votes
6answers
936 views
Is there a formula for $\sum_{n=1}^{k} \frac1{n^3}$?
I am searching for the value of $$\sum_{n=k+1}^{\infty} \frac1{n^3} \stackrel{?}{=} \sum_{n = 1}^{\infty} \frac1{n^3} - \sum_{n=1}^{k} \frac1{n^3} = \zeta(3) - \sum_{n=1}^{k} \frac1{n^3}$$
For which ...
1
vote
4answers
91 views
$\lim_{x\rightarrow\infty}\sin(x)$?
In physics I came across these kind of equations when I am trying to find the asymptotic behaviour of some function.
Can anyone explain if there is any sense in talking about $\sin(x)$ or $\cos(x)$ ...
1
vote
0answers
49 views
At large times, $\sin(\omega t)$ tends to zero?
While doing a calculation in quantum mechanics, I got a expression $\sin(\omega t)$, and my prof said if I consider the consider at large times, then i can assume that this goes to zero because at ...
1
vote
0answers
37 views
Conditioned probability in certain matrices with entries 0,1,$-1$
Consider $2\times n$-matrices with entries 0, 1 or $-1$, such that the number of zeroes in both rows is the same. Let $P_n$ be the probability that the first non negative element of both rows is a ...
2
votes
1answer
283 views
Prove $O(x)+O(x^2)=O(x^2)$ (Big O Notation)
I have to prove:
$O(x)+O(x^2)=O(x^2)$ for $x\to\infty$ where "O" is the Big-O-Notation
Specific functions are no problem for me, but I have some difficulties with this general form. But nevertheless ...
4
votes
2answers
133 views
Asymptotic behavior of sum of squares of combinatorial numbers with a weight.
Consider the following sequence of natural numbers,
$$M_n = \sum_{k=0}^n \binom{n}{k}^2 4^k$$
We can interpret $M_n$ as the cardinality of the set $X$ of $(2\times n)$-matrices with entries in ...
8
votes
2answers
100 views
Approximation of $\mathrm{Li}(x) = \int\limits_{0}^x \frac{dt}{\ln t}$ [duplicate]
I am reading about the Riemann hypothesis, and the article mentioned the Li function:
$$\mathrm{Li}(x) = \int\limits_{0}^x \frac{dt}{\ln t}$$
They said that this function can be approximated:
...
8
votes
2answers
339 views
How does Lambert's W behave near ∞?
How does $W$ behave near $+\infty$ compared to $\log$? In particular, I'm interested in the asymptotic expansion of
$$\frac{W(x)}{\ln(x)}$$
near $\infty$ (but along the positive real line, if that ...
1
vote
1answer
33 views
Big $\mathcal{O}$ notation for multiple parameters?
The following is an excerpt from CLRS:
$\mathcal{O}(g(n,m)) = \{ f(n,m): \text{there exist positive constants }c, n_0,\text{ and } m_0\text{ such that }0 \le f(n,m) \le cg(n,m)\text{ for all }n ...
