Tagged Questions

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

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 ...
1answer
22 views

0answers
63 views

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). ...
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$ ...
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 ...
2answers
45 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 ...
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 ...
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$. ...
0answers
31 views

We know the asymptotic density of primes. What about the asymptotic density of numbers with n prime factors? [duplicate]

Question in title. When I say n prime factors, I don't mean n distinct prime factors.
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 ...
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 ...
1answer
83 views

limit of sum with binomial coefficients

I have the problem to compute next double sum $$\sum_{n=2}^{\infty}\frac{(-1)^n}{n-1}\sum_{k=0}^{n}(3n-k)^j{n\choose k}A^{n-k}B^k\;,$$ being $j\gg1$ an integer number and ...
2answers
74 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 ...
1answer
76 views

1answer
48 views

Mean value of a subharmonic function, divided by the logarithm of radius, has a limit

I am pretty stuck on a homework problem on harmonic functions, or rather subharmonic functions (which for us are allowed to take the value $-\infty$). The statement is as follows: Supper $u$ is ...
1answer
56 views

Finding a minimum spanning tree in a graph with edge weights in {1,2,.., R} where R is constant

I have recently been doing some research into algorithms for finding minimum spanning trees in graphs, and I am interested in the following problem: Let G be an undirected graph on n vertices with m ...