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

Simplifying products

Sorry for the very general title, but I don't even know how to name my question. I got a formula which is: $f(n)=\prod_{i = 0}^{\infty} ((n \; \mathrm{rem} \; p^{i + 1}) \; \mathrm{div} \; p^i + 1) ...
2
votes
0answers
46 views

The characterization of asymptotic dimension

Let X be a metric space. The following conditions are equivalent (a)asdimX = n (b)n is the smallest integer such that for every R > 0 there exists n + 1 families Ui i=0,1,2,...,n, and S > 0 such ...
2
votes
0answers
181 views

representing integers as linear combination of integers

Let $a,b,a',b'$ be $r-\epsilon_1$ bit positive integers. Let $c,d$ be $s+\epsilon_2$ bit positive integers. Fix a pair $c,d$ and vary $a,b$ over all $r-\epsilon_1$ bit numbers. Do we have almost ...
1
vote
1answer
53 views

How to prove that sum given by generating function diverges for given value of $x$

I have a generating function: $A(x)=\dfrac{3-8x}{1-4x+6x^2-3x^3}$ (also I have a recurrence from which this function is built). I have to prove that sum $\sum\limits_k a_k\left(\dfrac{4}{3}\right)^k$ ...
1
vote
1answer
92 views

An integral relating to Bernoulli polynomials

Show that $$\int_{0}^{1}B_{2n+1}(x)(\cot({\pi}x)-2\sin(2{\pi}x))dx{\sim}0$$ where $B_{2n+1}(x)$ is the Bernoulli polynomials.
1
vote
1answer
61 views

Asymptotic equality proof with $a_n^2 \ln a_n ~ n$

Given $a_n^2 \ln a_n \sim n$, prove that $a_n \sim \sqrt{\frac{2n}{\ln n}}$. How do I approach this?
4
votes
1answer
112 views

Bernoulli number type asymptotics

I find an interesting formula but I can not prove it. Show that $$I_n=(-1)^{n+1}\int_0^1 B_{2n+1}(x)\cot(\pi x) \, dx\sim\frac{2(2n+1)!}{(2\pi)^{2n+1}}$$ where $B_n(x)$ is the Bernoulli Polynomials.
3
votes
2answers
145 views

Show $S(t) =\sum_{n=-\infty}^\infty\sin{(n^2t^2)}e^{-tn^2}$ is $O(t^p)$ at zero

An old qualifying exam problem: For $t>0$, define $$S(t) =\sum_{n=-\infty}^\infty\sin{(n^2t^2)}e^{-tn^2}.$$ Show that $S(t) = C t^p + o(t^p)$ as $t\to 0$ . Find $C$ and $p$. There are a couple of ...
3
votes
1answer
87 views

Asymptotic behaviour of e * !n - n! , n tends to infinity

What is the asymptotic behaviour of the function $e !n-n!$ , where $!n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}$ is the subfactorial of $n$. I tried Wolfram Alpha but the series for n=$\infty$ is ...
1
vote
0answers
52 views

Steepest descent?

Here I would like to see the behavior of a function as an integral when its argument (which is a parameter in the integral) goes to zero. If I try to evaluate an integral ...
0
votes
1answer
39 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
229 views

Asymptotic expansion of an integral

I came up with a simpler example which illustrates the technical difficulty I have encountered in my work. Consider an integral depending on parameter $\epsilon$: \begin{equation} ...
2
votes
2answers
78 views

Proof that asymptotic density $>1/n$ implies every sufficiently large integer is the sum of $n$ terms

Gerry Myerson commented on a previous question, which at the time asked for proof that every integer is a sum of two deficient numbers, "The deficient numbers have natural density strictly greater ...
0
votes
1answer
44 views

Power Series Expansion Asymptotics

From my text: Given $\cos^n(x),$ set $x=\frac{\omega}{\sqrt{n}}$, then a local expansion yields: $\displaystyle\cos^n(x)=e^{n\log\cos(x)}=e^{(-\frac{\omega^2}{2}+O(n^{-1} \omega^4))}$ ...
1
vote
1answer
413 views

Laplace transformation of a polynomial function involving square root (or approximation of the integral)

Could somebody suggest how to solve this Laplace transform: $$ \int_0^\infty{e^{-at}\over\sqrt{A+Bt+Ct^2}}{\rm d\,}t $$ ? The real coefficients $A,B,C$ are chosen such that the roots of $A+Bt+Ct^2$ ...
0
votes
1answer
28 views

Asymototics of a real sequence in a Riemann sum

Let $t<0$ and $f(k)\in O(|k|^{t})$ a real function, $k\in\mathbb{Z}$. We consider $$a_n\cdot \sum_{k=1}^n \frac{1}{n} \frac{f(k)}{n^t}$$ where $a_n\subset \mathbb{R}$ and ...
2
votes
2answers
31 views

Growth of series with decreasing numerators and increasing deonimators

It is known that $$H(n)=1+\dfrac12+\ldots+\dfrac1n$$ grows with the same rate as $\log n$. Therefore, $$nH(n)=n\left(1+\dfrac12+\ldots+\dfrac1n\right)=\frac n1+\frac n2+\ldots+\frac nn$$ grows with ...
4
votes
1answer
92 views

Asymptotics of coefficients in the expansion of $\log\cos x$

Let $c_n$ be the coefficient of $x^{2n}$ in the Maclauren expansion of $\log\cos x$. What can be said about the asymptotics of $c_n$ as $n\to\infty$? I expect that this question is routine, but I ...
1
vote
0answers
72 views

Boundary layer method

I am trying to solve the following differential equation using boundary layer method. $\psi ''(z) + \frac{1}{z} \psi'(z)(3 - \frac{4}{1+(\frac{z}{zc})^8})+ \frac{m^2}{1+(\frac{z}{zc})^8}\psi(z)=0$ ...
0
votes
1answer
43 views

Big Oh and Big Omega clarification

Can I get an explanation of: Can g(n) be Big O of $n^{2}$ and also the Big O of $n^{3}$? (at the same time) Can g(n) be Big Omega of $\Omega (n)$ and also be the Big O of $n$?
1
vote
3answers
74 views

Asymptotic relationship demonstration

I have to demonstrate that if $$ \begin{split} f_1(n) &= \Theta(g_1(n)) \\ f_2(n) &= \Theta(g_2(n)) \\ \end{split} $$ then $$ f_1(n) + f_2(n) = \Theta(\max\{g_1(n),g_2(n)\}) $$ Actually I ...
3
votes
0answers
90 views

Asymptotic solution for $T(n) = 6T(n/4) + n \lg n$

I am given that $T(n) = 6T(n/4) + n \lg n$ and want to find $\Theta(T(n))$. Below is what I have typed up for my solution so far; I asked my professor because I was unsure as to how I could assure ...
-1
votes
2answers
84 views

Prove that $f(n)=n^2+2^n$ is $\cal{O}(g(n))$, where $g(n)=3^n$

Prove that $f(n)$ is $\cal{O}(g(n))$, where $$f(n)=n^2+2^n$$ $$g(n)=3^n$$ I tried finding the limit using l'Hôpital's rule and breaking it into parts but it got too complicated.
0
votes
1answer
109 views

Derive asymptotic behavior of inverse of the normal cdf with respect to 2^n

I have a normal distribution $\mu = 0$ and $\sigma = 0.58n$ where $n > 0 $ and I am trying to derive the asymptotic behavior of the following equation: ...
3
votes
1answer
225 views

Asymptotic approximation of sum $\sum_{k=0}^{n}\frac{{n\choose k}}{2^{2^k}}$

I need to find the asymptotic approximation of this sum $$\sum_{k=0}^{n}\frac{{n\choose k}}{2^{2^k}}$$ Can you please share a link to theory or hint how it can be solved? Here is my attempt $n ...
0
votes
1answer
454 views

Is this true or false: $\sum_{i=1}^{n} \log(i)$ is the $ \Omega (n\log n)$?

I'm determining if $\sum_{i=1}^{n} \log(i)$ is the $ \Omega (n\log n)$. The summation of the above,$$\sum_{i=1}^{n} \log(i)= \log n!\approx n\log n$$ And checking with big omega $$n\log n \geq c ...
1
vote
2answers
40 views

Determine run-time of an algorithm

Probably a stupid question but I don't get it right now. I have an algorithm with an input n. It needs n + (n-1) + (n-2) + ... + 1 steps to finish. Is it possible to give a runtime estimation in Big-O ...
2
votes
1answer
167 views

How do you simplify this big O sum?

I saw someone interpret $\sum_{i=1}^{n}\mathcal{O}\left(i^{k-2}\right)$ as $\mathcal{O}\left(n^{k-1}\right)$. Is this right? If so, can you explain?
2
votes
2answers
57 views

What can we conclude from “f is not little-o of g”?

Given two functions $f$ and $g$, what does "$f$ is not $o(g)$" mean ? What can we conclude from this statement ? I know "$f$ is $o(g)$" means the limit at infinity of $\frac fg$ is zero. So does ...
1
vote
1answer
87 views

Find asymptotics in a given form $n=(e+o(1))^{f(s)}$

Let $p\to\infty$, $s={\binom {p^4} p}$ and $n={\binom {p^4}{p^2}}$. Find a function $f(s)$ in the following form $$\large n=(e+o(1))^{f(s)}$$ I've tried to use the followinf asymptotics for ...
1
vote
1answer
28 views

Approximating the modulus of a Complex Function near a point.

Let $\Omega$ be a domain in $\mathbb{C}$, and let $z_0 \in \Omega$. Let $f$ be analytic on $\Omega$. Let $z=z_0+re^{i\theta}$ for $r$ small. Assume that $f(z_0) \neq 0$ and $f'(z_0) \neq 0$. I want ...
3
votes
1answer
137 views

Find the constant $c$ in the equation $\max_{a\le n/2}\frac{C_n^a}{\sum_{k=0}^{\lfloor{a/3}\rfloor}C_n^k}=(c+o(1))^n.$

Find the constant $c$ in the equation $$\max_{a\le n/2}\frac{C_n^a}{\sum_{k=0}^{\lfloor{a/3}\rfloor}C_n^k}=(c+o(1))^n.$$ I've tried to use this asymptotics $$C_n^k \sim \frac{n^m}{m!} \sim e^{m\ln n ...
0
votes
1answer
34 views

Big-O evaluation:

I have the expression: $$f_{k}(n,m) = (n - k)(m - k) + f_{k+1}(n,m)$$ which runs until k = n or m. What is the big theta of this function in terms of n,m? A naive approach is to assume that m does ...
2
votes
3answers
500 views

What is the order of the sum of log x?

Let $$f(n)=\sum_{x=1}^n\log(x)$$ What is $O(f(n))$? I know how to deal with sums of powers of $x$. But how to solve for a sum of logs?
0
votes
1answer
47 views

Proving that if $f$ is equal to $g$ asymtotically then their distance tends to zero

How could I prove via limit definition that from $$ \lim_{n \to \infty} \frac{f(n)}{g(n)} = 1 $$ derives $$ \left| f(n) - g(n) \right| \to 0 $$ ? Previous attempt took me to $$ \left| f(n) - g(n) ...
5
votes
6answers
293 views

Asymptotic solution to the integral $\int_{-\pi/2}^{\pi/2} (\alpha + \sin x)^n \cos^2 x\,\mathrm{d}x$

Recently, I have posted a question on how to find a reduction formula for the trigonometric integral $$\int (\alpha + \sin x)^n \cos^2 x\,\mathrm{d}x.$$ This problem seems to be tough, however. When ...
1
vote
1answer
35 views

little-o and 3 functions

If we have 3 function $f$, $g$ and $h$ such that : $f$ is not $o(g)$ $f$ is $o(h)$ Can we conclude that $g$ is $o(h)$ ? i.e is the following true ? $lim_{x \rightarrow \infty} \frac{f(x)}{g(x)} ...
1
vote
1answer
47 views

getting T(n) when I get bigTheta complexity from recurrence relation

I wonder how could I solve the recurrence relation when I calculate complexities. Let me explain it via an example: $T(n)=2T(n/2) +n$. Solve this recurrence relation. I know from the Master theorem ...
5
votes
2answers
203 views

Find asymptotics of $x(n)$, if $n = x^{x!}$

Find the asymptotic for $x(n)$, if $n = x^{x!}$. I've tried 1) to take a logarithm: $x! \log{x} = \log{n}$. 2) to find $n'(x)$, using gamma-function for factorial $\Gamma(z) = \int_0^\infty ...
3
votes
1answer
190 views

Asymptotics for sums involving factorials

This question is rather general, but I have recently encountered the following situation in a variety of different settings. Let us suppose that we are given a complicated sum involving factorials ...
1
vote
1answer
51 views

Proof that $n^2 \not\in \omega(2^n)$

I'm trying to prove that $n^2 \not\in \omega(2^n)$ and I have to do it from definition. $f(n) \in \omega(g(n)) = \left\{f(n)| \forall c>0, c \in \mathbb{R}, \exists n_0 \in \mathbb{N}, \forall n ...
1
vote
1answer
188 views

running time of a multiplication algorithm

Here is a multiplication algorithm: given inputs x and y, add x to itself y - 1 times: z = 0 while y > 0: z = z + x y = y - 1 return z What is the running time of this algorithm? Is it ...
0
votes
1answer
59 views

consider the following subroutine, what is the running time

Suppose A(.) is a subroutine that takes as input a number in binary, and takes time O($n^2$), where n is the length (in bits) of the number. (a) Consider the following piece of code, which starts ...
0
votes
2answers
43 views

how long does this subroutine and loop take

Suppose A(.) is a subroutine that takes as input a number in binary, and takes linear time (that is, O(n), where n is the length (in bits) of the number). Consider the following piece of code, which ...
1
vote
2answers
66 views

big Oh notation of the smallest k

Recall the equivalence: $$m = 2^k , k = \log_2 m$$ (a) Consider the sequence: $$a_1 = 1; a_{k+1} = 2a_k$$ What is the smallest $k$ for which $a_k \geq n$? Your answer should be a function of $n$, and ...
2
votes
1answer
62 views

I have a Big-O Problem

I want to show: $(1-3z)^{3/2}$ is O(1-3z) as $z\rightarrow 1/3$ where $z \in \mathbb{C}$ I would like to be able to write: $\displaystyle \frac{(1-3z)^{3/2}}{1-3z}=(1-3z)^{1/2}$, and then show that ...
2
votes
3answers
229 views

how does the n-bit number related to big O notation

in algorithms you frequently have to evaluate problems like this, Let $x$ be an $n$-bit integer. For each of the following questions, give your answer as a function of $n$. my question is simple, ...
1
vote
2answers
163 views

Solving the recurrence $T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{2}\log(n)$

Please help me solve the recurrence $$ T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{2}\log(n) $$
1
vote
1answer
237 views

Calculating expected value of distance in a circle-circle intersection

Consider two circles $c_1$ and $c_2$ both of radius $r$ located in 2-D plane such that the distance between their centers is $r$. Assume a point is randomly and uniformly chosen within their ...
1
vote
1answer
112 views

Conditions for $o(|u|^{-1})$ decay of the Fourier transform of a bounded variation function

As the question suggests I am looking for a (not very restrictive) condition on a function of bounded variation so that its Fourier transform is $o(|u|^{-1})$ as $|u| \to \infty$. Let me elaborate on ...