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

learn more… | top users | synonyms (1)

19
votes
7answers
1k 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
162 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)$ ...
2
votes
0answers
110 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
42 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 ...
1
vote
0answers
140 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 ...
2
votes
1answer
108 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}) = ...
4
votes
2answers
182 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 ...
1
vote
1answer
98 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 ...
0
votes
1answer
38 views

Are these two definition equivalent?

$f(n) = \mathcal{o}(g(n))$ if for any constant $c$, there exists some constant $n_0$ such that $0 \le f(n) \le cg(n), n \ge n_0 $ $f(n) = \pi(g(n))$ if for any constant $c$, there exists ...
3
votes
4answers
198 views

Proving that $T(n) = 3T\left(\frac n3\right) + \sqrt n = \Theta(n)$

Show that $T(n)$ is bounded both above and below by $n$ (abusing the Big O notation) for some positive constants $c_1$ and $c_2$: $$ T(n) = 3T\left(\frac n3\right) + \sqrt n = \Theta(n) $$ ...
6
votes
4answers
319 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 ...
6
votes
1answer
123 views

Order of growth of derivatives at given x

Is there such an $f$ smooth function and $x\in D_f$, so that the sequence $f(x), f'(x), f''(x), ...$ grows faster than exponential? Can it grow at a factorial rate or faster?
5
votes
3answers
77 views

Question about $\Theta$

Can anyone give an example of a case where $f(n) = \Theta(g(n))$ for two positive functions and the limit $\lim\limits_{n \to \infty}\dfrac{f(n)}{g(n)}$ does not exist?
2
votes
1answer
50 views

Time complexity and proof of time complexity

Which is true and which false? I can't really decide which one is true and which false. Maybe in first 3 cases. $$3n^5 − 16n + 2 \in O(n^5)$$ $$3n^5 − 16n + 2 \in O(n)$$ $$3n^5 − 16n + 2 \in ...
0
votes
1answer
172 views

Proof of limit ratio theorem

My professor defines the Limit Ratio Theorem as follows: Assume that $\displaystyle\lim_{n \mapsto \infty} \frac{f(n)}{g(n)}=c$, where $c$ is a constant or $\infty$. If $0 \leq c < ...
1
vote
2answers
102 views

How can I analyze the asymptotic order of $n^{\ln n}$ and $(\ln n)^n$

I'm trying to analyze the asymptotic order of $n^{\ln n}$ and $(\ln n)^n$ At first, I take $\ln$ to both-hand-sides. So I got $(\ln n)^2$ and $n\ln(\ln n))$. However, I don't know what I should do ...
0
votes
1answer
80 views

Orders of Growth with Master Theorem

Determine whether each of the following statements is true or not. If true, provide a proof, if false, provide a counter-example. *(i) $f(n) = O(g(n)) \Rightarrow g(n) = \Omega(f(n))$ ...
2
votes
1answer
104 views

Large Deviations Problem

Let $\left(X_n\right)_{n\geq 1}$ be i.i.d random variables on $\left(\Omega,\mathcal A, \mathbb P\right)$, $X_1$ with mean $\mu$, and $$ L(\lambda) = \begin{cases} \log\mathbb E\left(e^{\lambda ...
8
votes
2answers
279 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: ...
2
votes
0answers
118 views

Upper bound for linear function

What may be more surprising is that when $a>0$, any linear function $an +b$ is $\mathcal{O}(n^2)$ which is easily verified by taking $c = a + |b|$ and $n_o = \max (\frac{-b}{a}, 1)$. $$an + b ...
1
vote
1answer
31 views

Questions on Strong mixing coefficients that satisfy $\alpha(m) = O(m^{-a-\epsilon})$

Say that we have strong mixing coefficients that satisfy the following: $\alpha(m) = O(m^{-a-\epsilon})$ for some $\epsilon > 0$. If we have $h\in {\mathbb N}$ that is finite and $h>m$, I have ...
1
vote
3answers
148 views

how to proof this big-oh statement?

I have a question on my homework which is: Prove that if $f(x)=O(g(x))$, and $g(x)=O(h(x))$, then $f(x) = O(h(x))$ I am not to sure how to prove this. This is my attempt. Is it good enough or am i ...
1
vote
1answer
278 views

Sum of the first k binomial coefficients for fixed n

I am reading Remarks on a Ramsey theory for trees by Janos Pach, Jozsef Solymosi and Gabor Tardos. Let $k, d, n \geq 2$ be integers. Somethig interesting happens when $$2^{n/k} > \sum_{i=0}^{d-1} ...
4
votes
1answer
158 views

Asymptotic Expansion

Can someone help me get an asymptotic expansion for $$\sum_{k=0}^n \frac{\ln(k+x)}{(k+x)}$$ at $n=\infty$, where $x$ is fixed, I need it with accuracy up to like $O(n^{-3})$, I expect there to be some ...
14
votes
2answers
696 views

Showing that $\lim_{n\to\infty}\sum^n_{k=1}\frac{1}{k}-\ln(n)=0.5772\ldots$

How to show that $$\lim_{n\to\infty}\left[\sum^n_{k=1}\frac{1}{k}-\ln(n)\right]=0.5772\ldots$$ No clue at all. Need help! Appreciated!
0
votes
1answer
204 views

Asymptotic/Big-O notation with multiple variables?

I'm a little confused with the following problem. Given two $n$-bit positive numbers $a; b$, compute $a^b$. How many bits does it take to write down the answer, in the asymptotic notation? I've ...
3
votes
1answer
62 views

$ (n-7)^2$ is $\Theta(n^2) $ Prove if it's true

$$ (n-7)^2 \, \text{is} \, \Theta(n^2) $$ Is this correct? So far I have: $ (n-7)^2 \, \text{is} \, O(n^2) \\ n^2 -14n +49 \, \text{is} \, O(n^2) \\ \begin{align} n^2 -14n +49 & \le \, C ...
0
votes
1answer
50 views

Questions concerning $\Omega$ and $\Theta$

How do I solve this: $\displaystyle\sum_{k = 1}^n \frac{k}{3}$ is $\Omega(n^2)$? I know that the summation would be $\displaystyle\sum\limits_{k=1}^n \dfrac{n^2+n}{6}$, but how do I solve ...
0
votes
1answer
89 views

Big-O Big theta Big omega papers

I'm studying algorithms complexities by myself (my university didn't it to me) and I'd love if someone could help me in finding good resources to learn fundamental algorithms complexities proofing. ...
1
vote
3answers
80 views

Question concerning big O

$\sum\limits_{i=1}^n(3i+2n)$ is $O(n^2)$ How do I solve this? I know that the answer for $\sum\limits_{i=1}^n(3i+2n)$ would be ...
2
votes
1answer
52 views

Two-point Taylor expansion with one assymptotic point?

According to this paper, a two-point Taylor expansion can be definied like this: $$\text{Let }f\left(z\right)\text{ be an analytic function and }z_1 \text{and }z_2\in \mathbb{C}, z_1\neq ...
1
vote
1answer
161 views

Where can I learn about solving Big-Oh problems that are written in algebra? [duplicate]

Where can I learn about solving Big-Oh problems that are written in algebra? Such as this $$\sum_{i=1}^{n} (3i + 2n) = O(n^2)$$
4
votes
2answers
455 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 ...
2
votes
3answers
222 views

What does O(n+k) mean verbally

I wonder the english explanation of O(n+k). Does it mean, the algorithm will run at most n+k times? Or does it mean the algorithm will run at most n or k times? And also is it same with O(n)+O(k)? ...
1
vote
1answer
1k views

What does it mean for a function to be polynomially bounded

There is a definition in my notes and says, When functions are polynomially bounded, the initial conditions (the value on small inputs) do not make a difference for the solution in ...
2
votes
1answer
84 views

How can I prove big-oh relation between $\log_2(\log_2 n)$ and $\sqrt{\log_2 n}$

How can I prove big-O relation between $f=\log_2(\log_2 n)$ and $g=\sqrt{\log_2 n}\,$? I want to find the constants, $c, N$ such that $\ g(x) \leq cf(x)$ for all $x>N$.
0
votes
1answer
45 views

Understanding Proofs Related to Limes and Landau Notation

We had to proove that if $f_1(x) = O(g_1(x))$ and $f_2(x) = O(g_2(x))$ for $g_i(x)$ > 0 then $i) f_1(x) + f_2(x) = O(g_1(x) + g_2(x))$ and $ii) f_1(x) + f_2(x) = O(g_1(x)g_2(x))$ Now I have ...
1
vote
1answer
88 views

Asymptotic Growth of Unitary Totient

What is the asymptotic growth rate of the unitary totient function, $\phi^*(n)$? It appears that $$\phi^*(n)\geq c\frac{n}{\ln n}$$ but I am sure there is a stronger lower bound. Any linkes to ...
0
votes
2answers
104 views

Sum with binomial coefficients and fraction

Is there a closed form known for $$ \phi(n,a,c)=\sum_{k=0}^n \binom{n}{k} a^k \frac{1}{k+c} $$ where $a <0$, $c>0$ and $n \in \mathbb{N}$? I know the answer for two special cases: $$ ...
0
votes
1answer
24 views

Is $(1+1/(x-1))^{x^\delta} > 2$ when $x > 1$ and $\delta \ge 1$?

Let $\delta>0$ be some fixed real number. I am interested in how $$(1+1/(x-1))^{x^\delta}$$ behaves when $x > 1$. In particular, I would like to know if $$(1+1/(x-1))^{x^\delta} > 2$$ holds ...
11
votes
3answers
309 views

Closed form for $\sum_{k=0}^{n} k\binom{n}{k}\log\binom{n}{k}$

Is it possible to write this in closed form: $$\sum_{k=0}^{n} k\binom{n}{k}\log\left(\vphantom{\Huge A}\binom{n}{k}\right)$$ Can you get something like $$n2^{n-1}\log(2^{n-1})$$
1
vote
1answer
79 views

Is my Big Oh proof correct?

I need pointers or corrections on my proof procedure. Prove $x^2 + 2x + 1 \in O(x^2)$: $x^2 + 2x + 1 \le cx^2$ $1+2/x+1/x^2 \le c$ This inequality holds for $x \ge 1$ and $c \ge 4$. Thus ...
11
votes
1answer
189 views

Calculate Asymptotics of Integral?

Let $f$ be a continuous function on $[0,1]$. How do I calculate the asymptotics, as $n\rightarrow\infty$, of $\displaystyle \int_{[0,1]^n}f\left(\frac{x_1+...+x_n}{n}\right)\text d x_1...\text d ...
6
votes
1answer
297 views

Missing term in series expansion

I asked a similar question before, but now I can formulate it more concretely. I am trying to perform an expansion of the function $$f(x) = \sum_{n=1}^{\infty} \frac{K_2(nx)}{n^2 x^2},$$ for $x \ll ...
0
votes
0answers
26 views

I don't understand how the sign of argument works in a function with arguments that could be positive, negative or in between

this formula is from http://en.wikipedia.org/wiki/Airy_function i want to know what is the value of Ai(large negative number) but if z is negative the formula below gives minusxminus = positive ...
2
votes
1answer
105 views

Theta asymptotic for $\binom{2m}{m}$ [duplicate]

Show that $\binom{2m}{m} = \Theta\left(\frac{2^{2m}}{\sqrt{m}}\right)$ without using Stirling's approximation.
0
votes
1answer
110 views

How to determine big O from expression?

If you have this expression: $$\frac{1+n+\left\lceil\log_2{n}\right\rceil}{1+\left\lceil\log_2{n}\right\rceil}$$ How do you obtain a big $O$ from this? I think it's just $O(\log_2n)$. Is this right? ...
2
votes
0answers
215 views

A proof of Stirling's Formula

I need to gain understanding of a proof of Stirling's formula. I have read through Tim Gowers' and Terence Tao's but I'm struggling to follow them. How rigorous is this proof, if at all? Thank you. ...
5
votes
1answer
108 views

Growth of $\Gamma(n,n)$

How can you get the asymptotics for the growth of $\Gamma(n,n)$? $$ \Gamma(n,n) = \int_n^\infty x^{n-1} \exp(-x) \mathrm{d}x $$
5
votes
3answers
162 views

Find a difficult limit

How can you prove $\lim_{n \rightarrow \infty} n\sum_{i=1}^{n-1}\frac{i(n-2)!}{(n-1-i)!n^{i+1}} = 1$? I know that $\sum_{i=1}^{n}\frac{i (n!)}{(n-i)!n^{i}} = n$ but I can't see how to get from one to ...