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
0answers
61 views

Bounding an implicitly defined sequence

I have a sequence $\lambda_0,\lambda_1,\ldots,$ which is defined implicitly as $$ \lambda_0 = \frac{1}{2},$$ and $$\lambda_{k+1} = \max_{\lambda\in[1,b]} \left\{\frac{1}{2\lambda}\prod_{0\leq ...
2
votes
1answer
81 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 ...
2
votes
3answers
489 views

Polynomial bounds?

Q1: Is the function $$\lceil{\lg n}\rceil!$$ polynomial bounded? Q2: Is the function $$\lceil{\lg\lg n}\rceil!$$ polynomially bounded? $$\lg = \log_2$$ Polynomially bounded: $f(n)$ is polynomially ...
1
vote
0answers
51 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 ...
12
votes
2answers
388 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
54 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 ...
10
votes
1answer
338 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 ...
3
votes
1answer
95 views

Asymptotics for infinite sum with erf

I'm interested in approximating the infinite sum $$ \sum_{i=1}^\infty Z\left(\frac{\alpha i\pm1}{\beta}\right) $$ where $\alpha,\beta$ are constant and $$ Z(a\pm ...
1
vote
3answers
131 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} ...
2
votes
0answers
45 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: ...
1
vote
4answers
99 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
43 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$?
0
votes
1answer
32 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
45 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
251 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
158 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 ...
1
vote
2answers
132 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
176 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
2answers
44 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
100 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
131 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 ...
8
votes
1answer
387 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
252 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 ...
1
vote
1answer
1k 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
435 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
44 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 ...
14
votes
2answers
568 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 ...
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
164 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
111 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
45 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
143 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
111 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
185 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
102 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
39 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
199 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
324 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
125 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
83 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
52 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
189 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
105 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
83 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
105 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
293 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
126 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
33 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
149 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
285 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} ...