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

learn more… | top users | synonyms (1)

3
votes
1answer
379 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
179 views

An issue with approximations of a recurrence sequence

By trying to give an approximation to a given recurrence sequence I encountered a problem. To be more precise I have a method but it fails if the right condition is not met and I wonder how I should ...
1
vote
1answer
57 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
39 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 ...
5
votes
1answer
191 views

Snags when discovering the asymptotic behavior of an integral

I have trouble in discovering the asymptotic behavior (i.e, the asymptotic expansion) of the following integral: $$\newcommand\abs[1]{\left\lvert#1\right\rvert} \int_0^{\pi/2}\frac{dx}{1+(n\pi+x)\sin ...
1
vote
1answer
61 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
64 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
511 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
52 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
415 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
55 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
345 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
99 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
142 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
44 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
33 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
46 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
292 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
166 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
139 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
182 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
45 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
101 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
132 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
451 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
303 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
2k 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
480 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
46 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
573 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
168 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
46 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
144 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
112 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
189 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
109 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
204 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
349 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
128 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
85 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
231 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
106 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
90 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))$ ...