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

learn more… | top users | synonyms (1)

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 ...
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
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 ...
3
votes
0answers
102 views

$2\times 2$ block Toeplitz determinant

My question is about computing asymptotic the determinant (dimension of the matrix $n\to\infty$) of a $2\times 2$ block Toeplitz matrix. $$\mbox{det}\left(\begin{array}{cc} a_n & b_n \\ d_n & ...
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. ...
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
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} ...
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} ...
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?
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
22 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
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
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$ ...
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 ...
2
votes
4answers
57 views

Intuition: Why will $3^x$ always eventually overtake $2^{x+a}$ no matter how large $a$ is?

I have a few ways to justifiy this to myself. I just think that since $3^x$ "grows faster" than $2^{x+a}$, it will always overtake it eventually. Another way to say this is that the slope of the ...
1
vote
1answer
31 views

Asymptotic of a convolution integral

$f(x) \ge 0$, $g(x) \ge 0$ are defined on $[0,\infty)$ and $f(x) \sim x^{-a}, \ x \to \infty$, where $a>1$. The integrals $\int_0^\infty f(x)dx<\infty$ and $\int_0^\infty g(x) dx<\infty$. ...
2
votes
0answers
31 views
1
vote
1answer
30 views

Asymptotic notation: What does $o(\epsilon_\text{mach})$ mean?

I'm having serious problems to understand what people mean when they write $o(\epsilon_\text{mach})$, where $\epsilon_\text{mach}$ stands for the machine epsilon. I'm seeing this in backward analysis ...
1
vote
2answers
22 views

How does the number of trees with even order that contain a perfect matching behave asymptotically?

I recently found a nice result for trees of even order that do not contain a perfect matching. This led me to wonder ‘how many’ trees have perfect matchings, asymptotically speaking. Is anything ...
0
votes
1answer
83 views

limit of sum with binomial coefficients

I have the problem to compute next double sum \begin{equation} \sum_{n=2}^{\infty}\frac{(-1)^n}{n-1}\sum_{k=0}^{n}(3n-k)^j{n\choose k}A^{n-k}B^k\;, \end{equation} being $j\gg1$ an integer number and ...
6
votes
2answers
75 views

Bounding a solution of an ODE with a small source

I have an ODE of the form $$ f''(x) + f(x) = \epsilon g(x)$$ with initial conditions $$ f(0) = f'(0) = 0 $$ $g(x)$ is $O(1)$ as $\epsilon \to 0$, and $g(x)$ is as smooth as necessary. Is there a ...
0
votes
1answer
76 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 > ...
2
votes
0answers
55 views

A limit about $\prod_{k=0}^\infty\frac1{1-x^k}$

If $$\sum\limits_{n = 0}^\infty {{a_n}{x^n}} = \prod\limits_{k = 0}^\infty {\frac{1}{{1 - {x^k}}}} ,$$ Prove $${a_n} < \exp \left\{ {\sqrt {\frac{{2\pi }}{3}n} } \right\}$$ and $$\mathop {\lim ...
0
votes
2answers
62 views

How to find the asymptotes of a square root function?

While working out some examples I'm trying to solve, I stumbled on a question that asks to find the asymptotes of the following function: $$y = \sqrt{x^2 + 3}$$ For rational functions I was thought ...
0
votes
0answers
14 views

Rate of growth of the negative part of even cumulants $(\kappa_{k})^{-}$ for mean zero, unit variance $X$

What is the rate of growth of $(\kappa_{2k})^-$ specifically in relation to $(2k)!$? The question was inspired by trying to find a lower bound for $$\kappa(t)+\kappa(-t)$$ by Taylor expanding ...
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
44 views

asymptotic analysis to solve differenial equation

$$ \frac{df(x)}{dx}+\bigg(1+\frac{1}{x}\bigg)f(x)=0 $$ how to solve above differential equation using asymptotic analysis ? Does that give an exact solution ?
1
vote
1answer
22 views

Use of asymptotically equivalent equations in limits

I was wondering about the steps to show that the following limit does not exists. $$\lim_{x\rightarrow\infty}[\log(x^2-3)-\log(x+2)]$$ I know that by using L'Hopital's Rule and the continuity of ...
1
vote
0answers
74 views

Asymptotic Expansion for a Function involving a Weird Integral

So I'm trying to find the asymptotic expansion as $x \to \infty$ of $$f(x)=\frac{1}{\bigg[A-\int \frac{\lambda^x}{\Gamma(x+1)}dx\bigg]^\frac{1}{\alpha}}$$ Note that $\lambda>0$ and $\alpha>0$. ...
0
votes
1answer
15 views

Complexity $\text{O}\left(\log(\log n))^{10}\right)$ vs $\text{O}\left((\log(\log n))^5\right)$?

If the question is not clear, then assume $t=\log(\log n)$, then the question can be re-framed as $\text{O}(t^{10})$ vs $O(t^5)$? So which has a higher order of growth? Thanks.
1
vote
0answers
24 views

Why can we act like functions are totally ordered by their orders?

For simplicity, consider only functions from $\Bbb N$ to $\Bbb R^{>0}$. Let $f\preceq g$ if there is an $A>0$ such that for all sufficiently large $n$, $f(n)\le A g(n)$. We normally would write ...
2
votes
2answers
35 views

Order of growth of the prime shift function

The prime shift function $s(n)$ for $n\in\Bbb N$ is defined by $$s\Big(\prod_ip_i^{e_i}\Big)=\prod_ip_{i+1}^{e_i},$$ where $p_i$ is the $i$-th prime. Here are the values of $s(1),\dots,s(100)$: ...
0
votes
0answers
24 views

Computation of $\sum_{i=0}^{m-1} n^{1/2^i}$

Basically, I'm just having issues computing this sum: $$ \sum_{i=0}^{m-1} n^{1/2^i} $$ where $m = \log_{2}({\log_{2}({n})})$. I need it in terms of $n$, as it's part of a runtime that I'm ...
2
votes
0answers
48 views

Nested trig asymptotics

Letting $\ \ \sin^n(x)=\underbrace{\sin\circ \sin\circ\dots\circ \sin(x)}_{n\text{ times}}\ $, is it true that $\ \ \sin^n(\pi/2)\sim \sqrt{\dfrac{3}{n}}?$ More specifically, is it true that ...
0
votes
0answers
17 views

Asymptotics of a series involving Incomplete Gamma function

The following is a series that involves Upper incomplete gamma function and I am trying to compute its asymptotics: $$ \frac{(n!)^2}{n^{2n+2}} \sum_{\substack{1 \leq i,j \leq n-1,\\\ 2\leq i+j \leq ...
0
votes
0answers
38 views

How small can we make two numbers $a$ and $b$, with prime factorizations such that…?

Given a number $n$, I'd like to find it using either the sum or difference of two other numbers. The other two numbers, which we can call $a$ and $b$, must have a prime factorization with no primes > ...
0
votes
1answer
65 views

Series Expansion within a fraction

I'm currently reading "The cumulant lattice Boltzmann equation in three dimensions: Theory and validation" from Geier et. al. and have some trouble in a proof. We have given multivariat cumulants ...
0
votes
1answer
42 views

Bounding a sum of logarithms

Consider a function $f:(0,\infty)\rightarrow \mathbb{N}$ with argument $\epsilon$. Suppose $f$ is decreasing in $\epsilon$. Let $0<b<1$, $K>0$, $d \in \mathbb{N}$, $\delta>0$. Assume $$ ...
2
votes
1answer
82 views

How do you refute these conjectures that seem imply contradictory statements?

I've formulated two conjectures that seems to imply a strong result when are combined with well known equivalences of the Riemann hypothesis, and I would like to know how get a disproof of such ...
0
votes
3answers
48 views

Asymptotic Expansion, Regular Perturbation

Regular perturbation. Find the first two terms in an asymptotic expansion of the small parameter $ϵ$ of the solution of $$ xy'+y=ϵy^{1/2},\quad x>0,\quad y(1)=1. $$ Explain why the expansion ...
1
vote
1answer
29 views

Asymptotic expansion of roots of function

Find expansions for all roots of the equations below as epsilon → 0 with two nonzero terms in each expansion I don't see how drawing the graph will help. Also how do I go about balancing the sizes ...
11
votes
1answer
160 views

On the theorem “$3$ is everywhere”

In this Numberphile video it is stated that "almost all natural numbers have the digit $3$ in their decimal representation", and a proof of this fact is proposed. A sketch of the proof follows: ...