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
2answers
242 views

limit of $\frac{(2n)!}{4^n(n!)^2}$

I'd love to understand the behaviour of the sequence $$ \frac{(2n)!}{4^n(n!)^2} \text{as } n \to \infty $$ the first step would be to simplify this to $$ \frac{(2n)(2n-1)(2n-2)\cdots(n+1)}{4^n \cdot ...
3
votes
1answer
105 views

Asymptotics of a mixture

Let $x_1, x_2 \cdots x_M$ be a sequence of iid random variables taking values over the integers, with $E(x_i)=0$. In particular, I'm interested in a shifted Poisson: $X=P-1$, where $P$ is Poisson with ...
3
votes
1answer
99 views

Euler numbers grow $2\left(\frac{2}{ \pi }\right)^{2 n+1}$-times slower than the factorial?

Stirling's approximation of the factorial for even numbers is given by $$ (2n)! \sim \left(\frac{2n}{e}\right)^{2n}\sqrt{4 \pi n}. \tag{1} $$ Further, the Euler numbers grow quite rapidly for large ...
4
votes
1answer
65 views

Asymptotics of $\sum_{i=1}^n {n \choose i}2^i \frac{i+1}{i^{\frac{n + 1}{2}}}$

I have the following formula which appears numerically to be exactly $4n$ asymptotically. $$\sum_{i=1}^n {n \choose i}2^i \frac{i+1}{i^{\frac{n + 1}{2}}}$$ What can one do to prove this?
2
votes
1answer
40 views

Asymptotics for $p$-series with $p=1/2$

Reading solutions to a practice exam, and I come across this: $$ O\left(\sum_{d \leq \sqrt{x}} {1 \over \sqrt{d}}\right) = O\left(x^{1/4}\right). $$ There are $O(\sqrt{x})$ terms in the sum, which ...
0
votes
1answer
204 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?
21
votes
9answers
3k views

What is the purpose of Stirling's approximation to a factorial?

Stirling approximation to a factorial is $$ n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n. $$ I wonder what benefit can be got from it? From computational perspective (I admit I don't ...
0
votes
1answer
47 views

a question concerning asymptotics

I have a rather simple question I need an answer to that I have been unable to answer and was wondering if anyone knew any results that pertain to this. It's very simple to state and I believe the ...
6
votes
3answers
85 views

Show that $\sum_{k=2012}^{n} 2^k\binom{n}{k} = \Theta(3^n)$

In this question we are asked to show that $\sum_{k=2012}^{n} 2^k\binom{n}{k} = \Theta(3^n)$ What I did: $\sum_{k=2012}^{n} 2^k\binom{n}{k} = \sum_{k=2012}^{n} 2^k*1^{n-k}\binom{n}{k} \leq ...
9
votes
2answers
326 views

Integral $S_\ell(r) = \int_0^{\pi}\int_{\phi}^{\pi}\frac{(1+ r \cos \psi)^{\ell+1}}{(1+ r \cos \phi)^\ell} \rm d\psi \ \rm d\phi $

Is there a closed form for $|r|<1$ and $\ell>0$ integer? The solution for the special cases $\ell=2$ and $4$ would also be interesting if the general case is not available. Integrating ...
2
votes
1answer
50 views

Show that $\operatorname{ln}(n!)=\Theta(n\operatorname{ln}(n))$

Another question about asymptotic approximations. We are asked to show that $\operatorname{ln}(n!)=\Theta(n\operatorname{ln}(n))$ I'm stuck tho and can use help. What I did is: ...
0
votes
0answers
32 views

check my short simple proof - Functions are of same magnitude. Asymptotic notation.

A simple question with a short solution I thought of, but I would like verification. $f(n)$ is a function that approaches infinity as $n$ approaches infinity. We are asked to show that ...
5
votes
1answer
119 views

PDE : Mixture of Wave and Heat equations

Today I was given the following equation : $$\frac{1}{c^2}u_{tt} + \frac{1}{D}u_t = u_{xx}$$ with initial conditions : $u(x,0) = 1$ if $|x|<L$ and $0$ otherwise, $u_t(x,0) = 0$. So fairly simple ...
0
votes
1answer
30 views

Check my short proof - asymptotic approximation, which function is bigger

The goal of this exercise is to show that $\ln(n+1)-\ln(n) = O(\frac{1}{n})$ what I did is: I used the fact that if $f=O(g)$ then $\frac{f}{g}=O(1)$. $\ln(n+1)-\ln(n)=\ln(\frac{n+1}{n}) = \ln(O(1))$ ...
2
votes
1answer
34 views

Problem finding limit - which function is asymptotically larger

I have a homework question, so please don't answer fully but I would appreciate a push in the right direction. Basically we need to figure out if $n^{n+\frac{1}{2}}e^{-n}$ is larger,smaller, or equal ...
7
votes
1answer
170 views

Asymptotic formula for almost primes

I have developed a formula for almost primes which is far more accurate asymptotically than Landau's well known $$\pi_k(n) \sim \left( \frac{n}{\log n} \right) \frac{(\log\log n)^{k-1}}{(k - 1)!}$$ ...
4
votes
1answer
29 views

Find asymptotics for solution $x$ of $(x+1)^{\frac{n+1}{n}}-x^{\frac{n+1}{n}}=5$

It is easy to see that for any $n\geq 1$, the equation $(x+1)^{\frac{n+1}{n}}-x^{\frac{n+1}{n}}=5$ has a unique positive solution ; call it $x_n$. Is there a simple asymptotic formula for $x_n$ ? I ...
3
votes
1answer
50 views

The statements $f(n) = O(n^{\epsilon})$ for all $\epsilon > 0$ and $f(n) = n^{o(1)}$.

Consider the statements \begin{align} \tag{A} f(n) &= O(n^{\epsilon}) \text{ for all } \epsilon > 0 \\ \tag{B} f(n) &= n^{o(1)} \end{align} Questions: It's clear that (B) implies (A). ...
4
votes
1answer
87 views

Finding a tight upperbound

A call graph $G = \{V,E\}$ on phone metadata has a vertex $v \in V$ for each phone number and an edge $\{v,w\} \in E$ if there has been a phone call between $v$ and $w$. One can monitor calls of a set ...
1
vote
1answer
63 views

$\pi(x)$ asymptotic as integral $1/\log t$

From the prime number theorem we know that $\pi(x)\sim x/\log x$, i.e. $\dfrac{\pi(x)\log x}{x}\rightarrow 1$ as $x\rightarrow \infty$. How can we use that to show that ...
2
votes
2answers
85 views

Proving a BIG-O statement? Logarithmic expressions. Simple Induction.

I have to write a proof for the following statement. $$\log_2(n!)\in\mathcal O(n\log_2(n))$$ What approach would you recommend. I am kind of LOST trying to figure this out. I transformed the ...
0
votes
1answer
24 views

Big-O problem, need help

f(n) = max(n^2, n^1.5 log^16 n) f(n) should be O(n^2),Omega(n^2), O(n^1.5 log^16 n), or Omega(n^1.5 log^16 n)? Can anyone help me with it and explain why?
1
vote
1answer
58 views

Is there an “interesting” function that grows faster than $n^{kn}$ but slower than $2^{2^n}$ — relates to understanding googolplex

Motivation: I'm looking for some sort of convenient fact I can use to grasp the size of a googolplex. For a googol we observe a convenient one; it's very nearly equal to 70!. But for a googolplex I ...
3
votes
1answer
67 views

Cesaro means and equivalent sequences

Let $(u_n)$ be a sequence of complex numbers that converges in mean (Cesaro convergence). Let $(v_n)$ be a sequence such that $v_n\sim u_n$. Does the sequence $(v_n)$ converge in mean? Here is ...
2
votes
0answers
53 views

Is it possible to find the least common divisor of a two numbers that are not relatively prime in polynomial time?

As the question states: Is it possible to find the least common divisor of two number that are not relatively prime in polynomial time? If so, how? Thanks!
3
votes
1answer
53 views

Equivalent of a recurrence sequence [duplicate]

Let $x_{0} = 2$ and $x_{n+1} = x_{n} + \ln(x_{n})$, how can I find an asymptotic equivalent of this sequence say, to the third term? (This is not homework, it was a problem in the Oral Examination ...
1
vote
1answer
62 views

Does proving that a function is not in big O mean that the function is in big Omega?

If I determine that a function is not in Big O of another function, can you assume that the function is in big Omega of the same function?
2
votes
1answer
38 views

$x^2-\log x = u $ asymptotic behaviour

Find the asymptotic behaviour as $u \to \infty$ of the solutions of $x^2-\log x = u$. Is there a standard method to solve this kind of problems? May the fact that we obviously know the derivative of ...
1
vote
1answer
30 views

Tight bound on the worst running time

I have to find a tight bound for an algorithm. I ended up with $3n^2 + 5$ as the worst running time of the piece of code. Is it ok if I consider $n^2$ as the tight bound? $$3n^2 + 5 \in ...
0
votes
3answers
58 views

Why $x=\pm1$ is not an asymptote of $\frac{x^3}{x^2+1}$?

By long division, $f\left(x\right)=\frac{x^3}{x^2+1}$is equal to $x-\frac{x}{x^2+1}$. Therefore, there is an asymptote $y=x$. But why there is no an asymptote $x=\pm1$? How to determine whether the ...
1
vote
0answers
26 views

Find the order of the following expression as x->0

Could someone help me find the order of the following expression without using the quotient rule? $\frac{1-\cos(x)}{1+\cos(x)}$ I expanded the denominator and the numerator but not sure how I get to ...
1
vote
0answers
26 views

Asymptotically evaluating integrals with oscillatory behaviour in both numerator and denominator

I have come across an integral that I would like to asymptotically evaluate (to leading order at least) which I have seen no mention of in standard textbooks. I want to evaluate an integral of the ...
1
vote
1answer
53 views

big O notation - explain the equality

$$\sum\limits_{i = 1}^{\log n} {\sqrt {{2^i}} } = O(n) $$ OK, So I understand the equality, but I don't know how to prove it. For my understanding, I need to show that the left side is $\le$ the ...
1
vote
0answers
64 views

How to prove that there are $O(T\ln T)$ zeros in the critical strip of the Riemann zeta function?

Define $F(T)$ as the number of solutions to $\zeta(a+ ti) =0$ for $0\le t\le T$ and $0<a<1$. How to show that $F(T)= O(T\ln T)$? For clarity, $\zeta$ is the Riemann zeta function, $i$ is the ...
4
votes
0answers
144 views

Double harmonic summation

I am interested in determining an asymptotic formula for the double summation of $1/(ab)$, where $a$ is an odd integer ranging between 1 and $k/\sqrt{j}$, $b$ is an odd integer ranging between $a$ and ...
0
votes
1answer
43 views

Big - Oh proof $n^{2^n} = O(2^{2^n})$

But the book asks me to prove that it's correct: $$n^{2^n} + 6*2^n = O(2^{2^n})$$ But I think, it's an incorrect one. Because, it's correct only for $n < 2$.
0
votes
1answer
56 views

Finding missing two edges in a MST in O(m) time

I need to write an algorithm in O(m) time to find the missing two edges of a minimum spanning tree. I am given a graph G(V,E) where m = |E| and n = |V| as an adjacency list, and T, a subset of G, with ...
1
vote
2answers
32 views

Growth rate of $1/(\log(x)-\log(x-1))$

Let $x>1$ be a real number. Let $y=\dfrac{1}{\log(x)-\log(x-1)}$. My question: Approximately how fast does $y$ grow (asymptotically) in terms of $x$? (e.g. linear, polynomial, exponential)?
6
votes
1answer
90 views

Limits of $\sum_{m=1}^{+\infty} \sum_{n=1}^{+\infty}e^{-mn x}$ at $0$ and $\infty$

Let $f(x) = \sum_{m=1}^{+\infty} \sum_{n=1}^{+\infty}e^{-mn x}$ for $x > 0$. Prove that $f(x) \sim e^{-x}$ as $x \to \infty$ and $\lim_{x\to 0} x\cdot (f(x) + \frac{1}{x}\log x)= \gamma$ where ...
0
votes
2answers
60 views

Proof that a circle has an infinite number of tangents

It seems obvious that a circle is comprised of the set of all points that are equidistant from one point, and that each point on the circumference of the circle represents a tangent. This seems to ...
8
votes
3answers
103 views

Sum $S(n,c) = \sum_{i=1}^{n-1}\dfrac{i}{ci+(n-i)}$

Consider the sum $$S(n,c) = \sum_{i=1}^{n-1}\dfrac{i}{ci+(n-i)}$$ where $0\le c\le 1$. When $c=0$, $S(n,c)$ grows asymptotically as $n\log n$. When $c=1$, $S(n,c)$ grows asymptotically as $n$. ...
0
votes
0answers
56 views

Method of Dominant Balance to find $\alpha$

I'm new to Asymptotic Expansions and am trying to understand how to use the method of dominant balance. Say are looking at a two term outer solution: $y=1+\epsilon(x-\log(x)-\frac{1}{x})$ I want to ...
2
votes
1answer
87 views

Asymptotic Expansion of a nearly divergent integral

I want to understand the asymptotic behavior of an integral of the form $$ I_f(\epsilon) = \int_0^1 \frac{\log(1/x)}{\sqrt{x}\sqrt{x+\epsilon}} f(x) dx $$ as $\epsilon \to 0^+$ for a generic function ...
3
votes
2answers
136 views

On proving the convergence of $1/n^2\sum_{1\le k\le n}\varphi(k)$

Let $$\Phi_n=\frac{1}{n^2}\sum_{k=1}^n\varphi(k).$$ How one can show that $\Phi_n$ is convergent sequence? (Here, $\varphi$ denotes the Euler's totient function.) And please, without any monster ...
2
votes
1answer
37 views

Asymptotic behaviour of the area of a 2-dimensional flat subset of $\mathbb{R}^3$

I am interested by the area of the $2$-dimensional flat subset of $\mathbb{R}^3$ defined by the following equations with one parameter $t>1$: $x,y,z>0$ (positive octant) $x+y+z=t$ (hyperplane ...
0
votes
1answer
30 views

Determine convergence or divergence of a slowly increasing sequence

We have by the integral test: $\sum_{n=2}^{\infty}\frac{1}{n}=\infty$ $\sum_{n=2}^{\infty}\frac{1}{n\ln n }=\infty$ $\sum_{n=2}^{\infty}\frac{1}{n\ln n (\ln\ln n) }=\infty$ ...
0
votes
1answer
301 views

Proving a tight bound on the worst case running time of an algorithm?

This exercise I don't understand what 'give a tight bound' implies here. The correct way to prove this is to consider that the runtime is in O and then use the definition of BIG O to prove that it ...
1
vote
0answers
33 views

Convergence in distribution and independence

Let $\{X_n\}_{n\geq1}$ and $\{Y_n\}_{n\geq1}$ be two sequences of random variables. Let $X$ and $Y$ be random variables and suppose $X_n \xrightarrow{d} X$ and $Y_n \xrightarrow{d} Y$. Furthermore, ...
-2
votes
2answers
62 views

How prove big O notation?

How to prove this function 1). $f(n)=n^3 − 5n^2 + 25n - 165$ is $O(n^3)$. 2)$3+\sin(1/n)$
0
votes
1answer
33 views

Recursive trees

Use the method of recursive tree to determine a good asymptotic upper bound (as tight as possible) for the following recurrence and prove your answer using induction (assuming that $T(n)$ is a ...