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
29 views

Need help with question regarding big O [duplicate]

In class we are currently covering upper/lower bounds, big Oh and omega and the like. I am pretty good on the "typical" functions one would do, but at a complete loss at "general" statements. This ons ...
1
vote
0answers
22 views

Asymptotic bounds of product of $\log(i)$

$$\prod _{k=2}^n\left(\log_2k\right)$$ Can somebody help me with bounds of this expressions. I see only the rude measure: $$\log_2n\le \prod _{k=2}^n\left(\log_2k\right)\le \left(\log_2n\right)^n$$
0
votes
0answers
33 views

How to prove or disprove $\forall f\in\mathcal{F}: \lfloor \sqrt{\lfloor f(n)\rfloor }\rfloor \in O(\sqrt{f(n)})$?

If $\mathcal{F}=\{f|f:\mathbb{N}\to\mathbb{R}^+\}$ How to prove or disprove $\forall f\in\mathcal{F}: \lfloor \sqrt{\lfloor f(n)\rfloor }\rfloor \in O(\sqrt{f(n)})$ . So I tried various functions ...
0
votes
1answer
32 views

Asymptotic expression for $\left(\frac{1}{\varepsilon}\right)^{\cfrac{1}{1-\varepsilon}}$

My question is regarding the expression below, where $\varepsilon\ll1$. $$\left(\frac{1}{\varepsilon}\right)^{\cfrac{1}{1-\varepsilon}}$$ Is it possible to express this in the form ...
0
votes
0answers
29 views

Need help with a question regarding the Big Oh

In class we are currently covering upper/lower bounds, big Oh and omega and the like. I am pretty good on the "typical" functions one would do, but at a complete loss at "general" statements. This ons ...
4
votes
1answer
59 views

Boundary layers: approximately satisfying BC

I am working on a boundary layer problem for a second order linear ODE. A simpler problem which I think still illustrates the issue I am having is $$\varepsilon y''-y'+y=0,y(0)=0,y(1)=1$$ where ...
0
votes
1answer
28 views

Proving that $2^{2n}-n^2+3^n = \Omega (2^{2n})$

I need to prove that: $2^{2n}-n^2+3^n = \Omega (2^{2n})$ I started and got to this: $2^{2n}-n^2+3^n \geq 2^{2n}\cdot 3 \geq 2^{2n}\cdot 2 = 2^{2n+1}$ for every $n > n_{0} = 1$ How should I ...
1
vote
1answer
20 views

How to prove that $8n^3 + 12n + 3\log^3n \neq \Omega (n^4)$?

How can I prove that $8n^3 + 12n + 3\log^3n \neq \Omega (n^4)$ ? I know that $8n^3 < 8n^4$ , $12n < 12n^4$ and $3\log^3n < 3n^4$ and then I can prove that $8n^3 + 12n + 3\log^3n = O(n^4)$ ...
0
votes
0answers
30 views

About asymptotic expansion of parabolic cylinder functions

Let's have the parabolic cylinder function $U(a,z)$. I'm interested in its asymptotics for large argument $z$. Here I've found it, but I'm a bit confuzed now because of expressions $(12.9.1)$ and ...
1
vote
0answers
18 views

Hypergeometric function asymptotics

When calculating the number of possible states of a spin 1 system in a magnetic field, one obtains the following expression $$\#\text{ of states} \propto \,_2 F_1 \left(-\frac{N-P}{2}, - \frac{N-P}{2} ...
0
votes
4answers
96 views

Prove $\log(n!) =\Omega(n\log(n))$ [closed]

Can someone help me prove that $\log(n!) =\Omega(n\log(n))$, that is, that there exists some positive $c$ such that, for every $n$ large enough, $\log (n!)\geqslant c\cdot n\cdot \log(n)$?
3
votes
0answers
33 views

Asymptotic bounds on the number of faces needed to construct a polyhedron of a certain genus

Let a polyhedron be a solid in three dimensions with flat polygonal faces, straight edges and sharp corners or vertices, where moreover we require that every edge touches exactly two faces, every ...
0
votes
0answers
28 views

Help with basic arithmetic involving Big Oh

I'm trying to determine the resulting "Big Oh" when arithmetic operators are applied between two different functions, but I'm a bit unsure after looking at even the basic operators shown on wikipedia ...
1
vote
1answer
37 views

Patterns in the plots of $\ln |\sin N|$ and $\ln | \cos N|$ for large integer $N$

Since no integer $N$ is a rational multiple of $\pi$ it's obvious that $\sin N$ and $\cos N$ will not give any 'nice' values for any $N$. Actually, I thought the values would get essentially random ...
3
votes
1answer
51 views

Deriving Stirling's approximation formula via the definition of the Gamma function

In my asymptotic analysis and combinatorics class I was asked this question: We first remember the definition f the Gamma function $ \Gamma(n+1) = n! = \int_{0}^{\infty} t^{n} e^{-t} dt $ and ...
1
vote
2answers
30 views

Expectation of a transformed random variable

I'm trying to prove the following: Let $X_n$ be a sequence of positive random variables and $g$ be a positive function. Suppose that $E[X_n]\to \infty$ as $n\to\infty$. If $E[g(X_n)]$ exists, there ...
0
votes
1answer
32 views

Troubles proving $O[f(n)] \cdot O[g(n)] = O[f(n) \cdot g(n)]$

Prove that $O[f(n)] \cdot O[g(n)] = O[f(n) \cdot g(n)]$, knowing that $O[g(n)] = \left\{ f(n) \mid \exists\ c,n_0 > 0\ :\ 0 \leq f(n) \leq c \cdot g(n)\ \forall\ n \geq n_0 \right\}$ I don't ...
0
votes
1answer
34 views

Correctness of Idea of Big O Proof

I have this big O proof and was wondering about the correctness of my rough work. Could anyone confirm if my idea for my proof is correct? Here is the question: Let ...
1
vote
1answer
47 views

On corollary and theorem involving autonomous 1st-order ODEs

Suppose we have an autonomous first-order ordinary differential equation $$\frac{dx}{dt} = f(x) \tag{*}$$ where $f$ is continuously differentiable for all $x \in D \subseteq \mathbb R$ s.t. the ODE ...
0
votes
1answer
35 views

On “bounded” in intuition for a theorem involving autonomous 1st-order ODEs

Suppose we have an autonomous first-order ordinary differential equation $$\frac{dx}{dt} = f(x) \tag{*}$$ where $f$ is continuously differentiable for all $x \in D \subseteq \mathbb R$ s.t. the ODE ...
1
vote
0answers
39 views

Help on Big O proof

I need some help with a big O proof. I think I have a proof but I feel like some of the steps aren't logically compatible. The Question: For all functions f,g with domain $\mathbb{N}$ that maps to ...
0
votes
2answers
53 views

Function with an asymptote at y=-1 and y=1

I'm looking for a function that has two asymptotes parallel to the x-axis. Preferably it should also only cross the x-axis at (0,0) and be built without using any trigonometric functions. Mind you, if ...
0
votes
1answer
21 views

Lower bound on binomial coefficient

Prove that $\binom{n}{k} ≥ \left(\frac{n}{k}\right)^k$ for integers $0<k<n $. I used Stirling formula to find the the combination of the left part but it goes very long and I can not find and ...
0
votes
0answers
32 views

Asymptotic to $f^{-1}(f ' (x)) $?

Let $tr(n)$ be the triangular numbers and $te(n)$ be the tetrahedral numbers. $$g(x) := \sum \frac{x^n}{n! 2^{tr(n)}}$$ $g'(x) = g(\frac{x}{2}) $ Now consider the analogue $$ f(x) = \sum ...
1
vote
1answer
48 views

Has limit $\frac{\sigma_0(n)\sigma_2(n)}{(\sigma(n))^2H_n},$ where $H_n$ is the nth harmonic number?

By specialization of an inequality I can write $$2 \sum_{k=1}^{n-1} \frac{1}{d_{k}} \sum_{l=k+1}^{n} \frac{1}{d_{l}}\leq 2\frac{\sigma_0(n)-1}{\sigma_0(n)}\cdot \left( \frac{\sigma(n)}{n} \right)^2, ...
1
vote
2answers
28 views

Big-O proof of inclusion

I'm working on this proof of inclusion:$$\log_2(8^n)\in{\mathcal O(n)}$$ $$\log_28^n-cn\leq0$$ for all $n>n_0$. Is there a log rule that I can use to further simplify before I plug random values to ...
0
votes
1answer
20 views

How to calculate $O(\sum_{k=1}^{K}(N-k)(k+1)^2)$?

Using the formula for the sum of the squares and the sum of first $K$ numbers I can get that: $$\sum_{k=1}^{K}(N-k)(k+1)^2=\dfrac{1}{12}K(-3K^2+2K^2(2N-7)+3K(6N-7)+26N-10)$$ Now I guess I can ...
0
votes
0answers
18 views

asymptotic expansion of an expression involving modified bessel function

I am looking for the asymptotic behavior of $$g(t,\nu)=e^{-t^2}\left[I_\nu(t^2)+\frac{1}{2}\left(I_{\nu+1}(t^2)+I_{\nu-1}(t^2)\right)\right]$$ as $t\rightarrow \infty$. Here $\nu$ only takes even ...
6
votes
1answer
112 views

Proportion of elements of prime order $p$ in $S_n$

I was trying to answer the following question recently : What is the proportion of elements of order $p$ in the symmetric group $S_n$ , where $p$ is some prime number ? I managed to work out that in ...
1
vote
1answer
50 views

What's about $\sum_{k=1}^{n-1} p_{k} \sum_{l=k+1}^{n} p_{l}$ for prime numbers?

By specialization of this formula, here in PROBLEMA 36, page 453 (in spanish), taking $\frac{1}{x_i}$ as the ith prime number we've (with at least two summands) $$ \left( \sum_{k=1}^{n} p_{k} ...
2
votes
2answers
61 views

Arrange the following:$(1.5)^n, n^{100}, (\log n)^3, \sqrt n\log n, 10^n, (n!)^2, n^{99}+n^{98}, 101^{16}$

Here is the question repeated: Arrange the following in order into increasing order of growth rates. $$(1.5)^n, n^{100}, (\log n)^3, \sqrt n\log n, 10^n, (n!)^2, n^{99}+n^{98}, 101^{16}$$ I graphed ...
1
vote
0answers
47 views

Complexity of FFT algorithms (Cooley-Tukey, Bluestein, Prime-factor)

I need to be able to explain the complexity of three Fast Fourier Transform algorithms: Cooley-Tukey's, Bluestein's and Prime-factor algorithm. Unfortunatelly, I'm a little lost in the process. ...
1
vote
1answer
22 views

Running Time Analysis

Here is the problem: sum = 0 for i = 1 to n for j = 1 to i^2 for k = 1 to j sum ++ Using three summations, $\sum_{i=1}^{n} \sum_{j=1}^{i^2} ...
4
votes
2answers
51 views

$\prod _{k=2}^{n} {\log k}$ is big-$O$ of what?

$$\prod _{k=2}^{n} {\log k}$$ is a big-$O$ of what? I can see it $O(n!)$ but is there a tighter solution?
2
votes
1answer
54 views

Evaluating $\lim_{x\to\infty}\frac{1}{x}\int_2^x M(t)\cdot f'(t)dt$, where $M(x)$ is Mertens functions

Let $\mu(n)$ the Möbius function. I know that combining Abel summation formula, the Prime Number Theorem and l'Hôpital's rule I can deduce $$\lim_{x\to\infty}\frac{1}{x}\sum_{2\leq n\leq ...
0
votes
1answer
32 views

Does any quadratic function in the form $an^2 + bn + c$ equal $\Theta(n^2)$ in asymptotic notation?

On a Khan Academy post (see here) about Big-$\Theta$ notation, the author attempted to convert the quadratic function $6n^2 + 100n + 300$ to asymptotic notation. They started by dropping the $n^2$ ...
1
vote
0answers
46 views

Sum of first n primes [duplicate]

Can we claim it is asymptotic to $n^2\log n$? I argue that because $p_n\sim n\log n$, we can say: $$\sum_n n\log n=\log1+2\log2+\dots+n\log n$$ $$=\log1+\log2+\dots+\log n$$ $$+\log2+\dots+\log n$$ ...
1
vote
1answer
28 views

Averaged Multinomial Coefficient

Following on from the asymptotic value of the central binomial coefficient, namely: $$\dbinom{2n}{n}\sim\dfrac{4^n}{\sqrt{\pi n}}$$ we have the multinomial coefficient: $$\dbinom{n}{k_1 k_2\dots ...
4
votes
0answers
23 views

What is known about the counting function of Gaussian primes"

The counting function of primes among $\Bbb{N}$, describing the asymptotic density of the primes, is well known (the Prime Number theorem). Let's define a mild generalization of the counting function ...
0
votes
1answer
64 views

Prove that $1^3 + 2^3 + \cdots+n^3$ is $O(n^4)$ [closed]

I suppose I am not exactly familiar with the process for finding the "Big-O" of this problem. Isn't the highest term still to the 3rd degree? $(n^3)$ which would make me think that it is $O(n^3)$, ...
2
votes
0answers
38 views

Estimating the number of permutations with no increasing subsequences of a prescribed length

Let $n\geq 1$ be a positive integer and let $S_n$ be the set of permutations of $\{1, \dots, n\}$ (thought of as non-repeating, exhaustive sequences of elements of $\{1, \dots, n\}$. Let $2 \leq k ...
1
vote
0answers
63 views

What is the limit inferior of $p_n^2/ (\log p_n) \left\lvert 1-e^\gamma\log(p_n+\log^2p_n+\varepsilon_n)\prod_1^n (1-1/p_k)\right\rvert$?

Let $p_n$ be the $n$-th prime number. The $\varepsilon_n:=\varepsilon(p_n)$ in the title is an infinitesimal sequence chosen so that, replacing $p_n$ with $x$, we have$$\lim_{x\to+\infty} ...
1
vote
1answer
8 views

Asymptotic relations at infinty

I am attempting to show that If $f(x) - g(x) \ll 1,\, x \to \infty$, then $e^{f(x)}\sim e^{g(x)}, \,x\to \infty$ From the first line, I am able to show that $$ \lim_{x\to \infty} \frac{f(x) - ...
0
votes
1answer
25 views

Stochastic Convergence Intermediate Textbooks

Currently doing a course in asymptotic theory and wanted to deepen my knowledge about stochastic convergence and related topics. The textbook we are given is "Asymptotic Theory for Econometricians" by ...
0
votes
0answers
21 views

calculate nCr given (n-1)C(r-1) under a modulo fast

Let $_nC_r$ be n choose r or $\frac{n!}{(r!*(n-r)!)}$ Given the value of $_nC_r$ for some n, r, equal to k, how could one find $_{n+1}C_{r+1}$ (mod m) fast computationally (small asymptotic time). ...
0
votes
1answer
77 views

Is $\log(3^n) = O(\log(2^n))$?

How can I prove that this is true/false: $$\log(3^n) \in O(\log(2^n))$$ I know $f(n)$ is $O(g(n))$ if there are positive constants $C$ and $k$ such that: $$f(n) \le C \cdot g(n)$$ whenever $n > ...
0
votes
0answers
19 views

Asymptotic Expansion for Function with an Embedded Integral [duplicate]

So I'm trying to find the asymptotic expansion as $x \to \infty$ of: $$f(x)=\frac{1}{\bigg[A-\int_{x_0}^x\frac{\lambda^y}{\Gamma(y+1)}dy\bigg]^{\frac{1}{\alpha}}}$$ where $x_0>0$ and $\alpha>0$ ...
28
votes
4answers
4k views

Prove that this function is bounded

This is an exercise from Problems from the Book by Andreescu and Dospinescu. When it was posted on AoPS a year ago I spent several hours trying to solve it, but to no avail, so I am hoping someone ...
0
votes
1answer
54 views

Find the Theta class for the recursion $T(n) = T(3n/4) + T(n/6) + 5n$

$\displaystyle T(n) = T\left(3n\over4\right) + T\left(n\over6\right) + 5n$ is not in the proper form for the Master theorem so I can't really apply it. The only idea I had was changing the ...
0
votes
2answers
46 views

Can I prove that 2n+1 = O(2n)?

Is 2n+1 = O(2n)? In other words, 2n+1 <= c * 2n for any c and all n > n0? I have plugged in numbers but none that worked. Obviously It is also (n) but I am trying to prove the above. Much ...