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
1answer
252 views

Master Theorem when B is a fraction.

So I'm working through my homework, and applying the Master Theorem pretty easily, then my prof throws me a curve ball $T(n) = 4T(3n/4) + n^4$ Now I used my usual steps of listing out what A, B, ...
1
vote
1answer
56 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
94 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.
4
votes
1answer
118 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.
1
vote
1answer
69 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?
3
votes
1answer
91 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 ...
3
votes
2answers
247 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} ...
1
vote
0answers
64 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 ...
2
votes
2answers
80 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))}$ ...
2
votes
1answer
236 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?
0
votes
1answer
29 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 ...
3
votes
1answer
241 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 ...
1
vote
1answer
143 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 ...
3
votes
2answers
34 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
95 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 ...
3
votes
0answers
99 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 ...
0
votes
1answer
44 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$?
4
votes
1answer
145 views

Prove Linearity in Asymptotic Notation

The question: Prove O($\sum\limits_{k=1}^m(f_k(n))$) = $\sum\limits_{k=1}^m(O(f_k(n)))$ What I have done so far: Left side: Let g(n) = O($\sum\limits_{k=1}^m(f_k(n))$) For n > c, we have g(n) $\le$ ...
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 ...
-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
120 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: ...
2
votes
1answer
184 views

Asymptotics for sum of binomial coefficients

Could you give me a hint how to find $c$ in the asymptotic for the sum: $$ \sum_{k=0}^{\lfloor {n}/{2} \rfloor}\binom{n-k+1}{k}=(c+o(1))^n $$ and for $$ \max\limits_{a\leq ...
1
vote
1answer
44 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)} ...
0
votes
1answer
732 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 ...
3
votes
1answer
164 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 ...
14
votes
3answers
566 views

Order of the smallest group containing all groups of order $n$ as subgroups.

Let $n\in \Bbb N$ be fixed and $m\in \Bbb N$ be the least number such that there exists a group of order $m$ in which all groups of order $n$ can be (isomorphically) embedded. Can we deduce $n!=m$?
2
votes
2answers
58 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 ...
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 ...
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 ...
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 ...
3
votes
1answer
204 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 ...
2
votes
3answers
834 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?
5
votes
1answer
171 views

Find asymptotic for $s(n)=\min\{m\in{\mathbb N}\mid C_n^m\cdot e^{-m^3/(\ln m)^{10}}<1\}$

I have some strange function: $s(n)=\min\{m\in {\mathbb N} \mid C_n^m\cdot e^{-m^3/(\ln m)^{10}}<1\}$ and I need to find asymptotics for it. I have a solution for this except one last step, I ...
0
votes
1answer
48 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
307 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 ...
5
votes
2answers
223 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 ...
1
vote
1answer
52 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
49 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 ...
1
vote
3answers
1k views

Show that $(n + a)^{b}$ = $\Theta(n^{b})$

In the book I'm following I got the following solution: To show that $(n + a)^b = \Theta(n^b)$, we want to find constants $c_1, c_2, n_0 > 0$ such that $$0 \leq c_1 n^b \leq (n + a)^b \leq c_2 ...
1
vote
1answer
213 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
71 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 ...
1
vote
2answers
74 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 ...
14
votes
3answers
512 views

Can a function “grow too fast” to be real analytic?

Does there exist a continuous function $\: f : \mathbf{R} \to \mathbf{R} \:$ such that for all real analytic functions $\: g : \mathbf{R} \to \mathbf{R} \:$, for all real numbers $x$, there exists ...
1
vote
1answer
269 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 ...
2
votes
3answers
318 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, ...
2
votes
2answers
186 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) $$
0
votes
2answers
72 views

Meaning of $O(n)$ in an expression

As my mathematical knowledge is increasing, I have been seeing more and more of $O(n)$ implementation in expressions. Here is what I mean. Example: $$z^{q_{N+1} + q_N} w^{q_{N+1} + q_N} (-1)^N (w-1)/w ...
1
vote
1answer
299 views

big-O proof with power functions

I was wondering if anyone could show a proof for why $a^x$ is $\mathcal{O}(b^x)$ if $a$ and $b$ are constants and $a < b$. In other words, with power functions, does the function with the largest ...