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

Asymptotics of two expressions involving logarithms

(As I am new to algorithmic complexity so), EDIT: please give solutions for large x (means as x->infinity) !
3
votes
1answer
144 views

Bound of the sum $\sum_{p\le n}\frac{1}{\log(p)}$

While doing a sum I came to the sum $\displaystyle\sum_{p\le n}\dfrac{1}{\log(p)}$. Where the $\log$ is the natural logarithm. It was easy to prove that $\displaystyle\sum_{p\le ...
1
vote
0answers
68 views

Newton polygon and asymptotic behavior near a singular point

As we know, Newton polygons could be used to determine the Puiseux series of algebraic curves (see, for example, Kirwan's Complex Algebraic Curves, chapter 7). Different branches correspond to ...
7
votes
0answers
78 views

Partitioning points with a line

Let $A_{m, n} = \{1, 2, \dots, n\} \times \{1, 2, \dots, m\}$. A straight line would partition the points into two sets. How many ways are there to do it? Let $p_{m, n}$ be that number. Apparently ...
4
votes
2answers
479 views

Understanding definition of big-O notation

In a textbook, I came across a definition of big-oh notation, it goes as follows: We say that $f(x)$ is $O(g(x))$ if there are constants $C$ and $k$ such that $$|f(x)| \le C|g(x)|$$ whenever $x \gt ...
1
vote
2answers
117 views

What is the order of growth of the parameterized recurrence relation given below?

Given two parameters $a$ and $b$ (both positive integers), please estimate the order of growth of the following function: $$F(t)=\left\{\begin{array}{ll} 1, \, &t\le a \\ F(t-1) + b\cdot ...
16
votes
4answers
643 views

Decreasing integers on the blackboard

There are $n\geq 2$ copies of an integer $k>0$ written on the blackboard. A move consists of choosing an integer $m>0$ on the blackboard, and replacing it as well as one other integer on the ...
2
votes
2answers
231 views

Asymptotics of ${2^n \choose n}$?

How can one compute the asymptotics of ${2^n \choose n}$? I know it is bounded below and above by $\left(\frac{2^{n}}{n}\right)^n$ and $\left(\frac{2^{n}e}{n}\right)^n$. If I plug in Stirling's ...
1
vote
0answers
42 views

Can I use the Big-O (Landau) notation to “segment” the set of positive increasing real functions?

Let functions $f(n)$ and $g(n)$ be increasing in $n$. I am trying to say the following precisely: As $n\rightarrow\infty$, if $f(n)$ is "smaller" than $g(n)$ then $A$ is true, and if $f(n)$ is ...
7
votes
1answer
179 views

Order and type of an entire function $f$ such that the numbers $f^{(n)}(0)$ are integers.

Let $f$ be an entire function with order $p=1$ and such that the numbers $f^{(n)}(0)$ are integers. Then show that the type $\sigma$ is at least $1$. I appreciate any suggestions.
1
vote
3answers
47 views

I have an answer for an asymptotic analysis, which i cannot accept. please explain me where i go wrong.

We have the following function definitions: \begin{align*}f_1 (n) &= n^{n^{\frac{1}{2}}} \\ f_2 (n) &= 2^n \\ f_3 (n) &= n^{10} 2^{\frac{n}{2}} \\ f_4 (n) &= \sum_{i=1}^{n} (i+1) ...
21
votes
2answers
1k views

A (non-artificial) example of a ring without maximal ideals

As a brief overview of the below, I am asking for: An example of a ring with no maximal ideals that is not a zero ring. A proof (or counterexample) that $R:=C_0(\mathbb{R})/C_c(\mathbb{R})$ is a ...
1
vote
0answers
26 views

Can an entire $f$ satisfy $x>k | f(x+yi)=\ln(x+yi+z)+o(1) $?

Let $z$ be a complex number. Let $i$ be the imaginary unit. Let $x,y,k$ be positive real numbers. Consider $$x>k | f(x+yi)=\ln(x+yi+z)+o(1) $$ true for all $x>k,y$ and some $k,z$. Is there ...
0
votes
1answer
38 views

Asymptotic distribution of $\left(1-\frac{1}{n}\right)^{n\bar{X}_n}$

Suppose $X_1,X_2, \cdots$ are i.i.d. observations from a $Poisson(\lambda)$ distribution. Define $\bar{X}_n=\sum_{i=1}^nX_i/n$. What will be the asymptotic distribution of ...
2
votes
2answers
267 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
109 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
160 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
75 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
48 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 ...
21
votes
9answers
5k 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
51 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
105 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 ...
10
votes
2answers
358 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
56 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: ...
7
votes
1answer
215 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
42 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
53 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
211 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
34 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
57 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
104 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
72 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
149 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
31 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?
3
votes
1answer
96 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 ...
3
votes
1answer
61 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
84 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
55 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
39 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
63 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
30 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
42 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
109 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
69 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 ...
0
votes
1answer
50 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
90 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
39 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
98 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 ...
8
votes
3answers
117 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$. ...
2
votes
1answer
112 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 ...