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
2answers
32 views

Asymptotic Expansion of $\ f(x)=(1-\beta \frac{ log(log(x))}{log(x)})^{\beta}$

So I got this function and I'm looking for an asymptotic expansion for different values of$\ \beta > 1 $ $\ f(x)=\left(1- \beta \frac{\log \left( \log(x) \right)}{\log(x)} \right)^{\beta}$ as $\ x ...
4
votes
1answer
474 views

Can a curve be an asymptote?

$f(x)=x^3+\frac{3}{x-1}$ This was the question given to me.I replied that $f(x)$ will have only a single vertical asymptote of $x=1$. My teacher told that there'll be be two asymptotes.One is the ...
2
votes
1answer
111 views

Asymptotic behavior of the minimum eigenvalue of a certain Gram matrix with linear independence

Consider the density matrices with the following spectral decompositions: $$\rho=\lambda_1|\nu_1\rangle+\lambda_{2}|\nu_2\rangle$$ and $$\sigma=\gamma_1|\omega_1\rangle+\gamma_2|\omega_2\rangle$$ such ...
1
vote
2answers
37 views

Sum over values of auxiliary function gets arbitrary big, justification

Let $f : \mathbb N_{>0} \to \mathbb R_{\ge 0}$ be a function satisfying $\sum_{n=1}^{\infty} 2^{-f(n)} = \infty$ (like $f(n) = \log n$). Define $$ F(n) = \left\lfloor \log_2\left( \sum_{i=1}^n ...
1
vote
1answer
62 views

Asymptotic expansion of integral with hyperbolic functions

Consider the integral given by $$f(r)=\int_{0}^{\tanh(r)} \arccos\left(\frac{\sigma}{\sinh(r)\sqrt{1-\sigma^2}}\right)\cdot \frac{1}{\sqrt{\sigma^2+a^2}}d\sigma,$$ where $a>0$. I am wondering ...
1
vote
1answer
26 views

Asymptotic probability that two integers are coprime

I'm having difficulty with a number-theory-type exercise. Could you provide assistance with computing the asymptotic probabilities that two integers are coprime (both integers tending to $\infty$), ...
3
votes
3answers
45 views

Which is greater as $n$ gets larger, $f(n)=2^{2^{2^n}}$ or $g(n)=100^{100^n}$?

It is the first time I met such a question: Which is greater as $n$ gets larger, $f(n)=2^{2^{2^n}}$ or $g(n)=100^{100^n}$? Intuitively I think $f(n)$ would gradually become larger as $n$ gets ...
0
votes
0answers
18 views

Asymptotic series of a matrix-valued function.

Consider the following matrix $$f(\lambda)=\left( \frac{\lambda-1}{\lambda + 1} \right)^{\nu \sigma_3} \ \ \ \lambda \in \mathbb{C} \setminus [-1,1]$$ where $\sigma_3=\begin{pmatrix} 1 & 0 \\ 0 ...
2
votes
0answers
26 views

Integral and derivatives of the gamma function

Here is my question: Starting from the relation $$\int_{0}^{+\infty}t^{a-1}e^{-nt}\,dt=n^{-a}\Gamma(a)\qquad a>0$$ and differentiating $m-$times under the integral sign we can get to ...
0
votes
2answers
31 views

Arter there any 'Horizontal Asymptote' rule exceptions?

An equation I have is $$F(x) = \frac{9x(x-9)}{3x^2-11x-4}.$$ Upon calculating using the rules taught in class, There is an H.A. at $y = 3$ and a V.A. at $x = -\frac13$ and at $4.$ After graphing, ...
2
votes
2answers
73 views

Is $\lim S_{n,m}=\sum_{k=1}^n({-1})^k{n\choose k}k^{-m}<\infty $ for $ n \to \infty$ and $m$ large?

Let $m$ be a positive integer and let $$S_{n,m}=\sum_{k=1}^n({-1})^k{n\choose k}k^{-m}$$ be a partial sum of real series . My question here is :Is $\lim S_{n,m} <\infty $ for $ n \to \infty$ and ...
2
votes
0answers
20 views
+50

Derivatives of $O$-regular varying functions are $O$-regular varying functions?

The Monotone Density Theorem for regularly varying functions says, in essence: Theorem (Monotone Density Theorem). Let $f$ be a differentiable regularly varying real-function of index $\rho$ ...
1
vote
0answers
15 views

Growth analysis: fractional power functions dominate polylogarithmic?

In big-O notation for algorithmic time-complexity analysis, given real-valued functions $f$ and $g$, $f(x)$ is $O(g(x))$ if there are constants $C$ and $k$ such that $$ |f(x)| \leq C |g(x)| \quad ...
1
vote
2answers
56 views

Can $O(\sqrt{x})$ be considered $o(x)$?

This example challenges my understanding of $O(x)$ and $o(x)$ notation. One the one hand I have: $$ A = B + o(x)$$ Another part of the paper uses big-O instead of little-o and says: $$ C = D + ...
1
vote
1answer
29 views

Asymptotic Expansion of $\ f(x)=\frac{\log(x)}{\frac{\log(x)}{2\alpha}-\log(\log(x))}$

I'm looking for the asymptotic expansion as $\ x \rightarrow \infty$ for $\ f(x)$ for small $\alpha$. Ideally, I'd like to get the asymptotic expansion for all orders. How would I go about doing this? ...
1
vote
1answer
23 views

How is this example big-omega?

I'm having a bit of difficulty understanding big-omega and big-theta of this particular function which is supposedly Ω(16n + 33) $5n − 2 = Ω(16n + 33)$ I understand that the there is some constant c ...
2
votes
1answer
48 views

A sum involving twin primes and Prime Number Theorem

This morning I've been watching documentary about asterorids, in a scene an astronomer explains the so called image subtraction process or pixel subtraction, a mathematical model used in computerized ...
1
vote
1answer
28 views

Prove there exists a constant $K>0$ such that $|e^z-1-z-\frac{z^2}{2}|<K|z^3|$ as $z \to 0$

The title says it all however: Prove that there exists a positive constant $K$ such that $|e^z-1-z-\frac{z^2}{2}|<K|z^3|$ when $|z|$ is sufficiently small. Or in other words prove ...
0
votes
1answer
65 views

Asymptotics of function of $n^a$, $2^n$ and $\sqrt{n}$, when $n\to\infty$

I am having trouble with estimation of the following$$\frac{n^a}{2^{n-\frac{\sqrt n+1}{2}}(1-\frac{1}{2 \sqrt n})^{n-\frac{\sqrt n-1}{2}}} $$ Where $n \in N$ and $a$ is a real number greater or equal ...
0
votes
2answers
28 views

Why does the Big Oh (and similar) notations needs $n_0$?

The generally agreed definition of the Big Oh notation (afaik) is as follows: The function $f(n)$ is $O(g(n))$ if there exists constants $c$ and $n_0$ such that for all $n \ge n_0$, $f(n) \le c ...
3
votes
0answers
65 views
+50

Asymptotic form of an integral to an power law decaying function

$$ f(x)=\frac{1}{2}+\frac{1-x^2}{4x}\ln\left|\frac{1+x}{1-x}\right| $$ This function is not analytic at $x=1$. The plot is shown: The integral is: $$ I=\int_0^\infty g(x) \sin(2b rx) dx $$ where ...
0
votes
2answers
33 views

If $f(x)=o(\log^{(k)}(x))$ for all $k$, can $f$ diverges?

Is there a divergent monotone non-decreasing continuous positive real-function $f$ such that $$\lim\limits_{x\to +\infty} \frac{f(x)}{\log^{(k)}(x)} = 0$$ for all $k\geqslant 1$? (By ...
0
votes
1answer
28 views

Asymptotic Inequality in Probability

Given that $P(X>a)\leq f(a)$. Now, $f(a)$ tends to zero faster than $P(Y>a)$. Does it mean that $(1)P(X>a) \leq P(Y>a)$ or $(2)P(X>a) \geq P(Y>a)$ as $a \rightarrow \infty$.
1
vote
0answers
24 views

asymptotics of Involutions recurrence relation

Consider the following recurrence relation where $t(n)$ is the number of involutions on $\{1,...,n\}$ \begin{equation} (n+1)t(n)+t(n+1)-t(n+2)=0 \end{equation} When $n \rightarrow \infty$, Wimp and ...
2
votes
0answers
46 views

Recurrence equation approximation

I have the following recurrence relation, $$x_{i+1}=a\cdot x_i^{\frac{2-2\alpha}{3}}+x_i,$$ where $a>0, \alpha>0$, and $x_0>0$. My goal is to get an approximate the expression for $x_i$. I ...
0
votes
0answers
14 views

dominant balance for coupled differential equations

I have been trying to solve following set of nonlinear differential equations: $\frac{dy(t)}{dt}=k z(t) - 3 k y(t) - y(t)^2 + \epsilon_1 (M-z(t))^2$ $\epsilon_2 \frac{dz(t)}{dt}=Mz(t) - z(t) y(t) - ...
1
vote
0answers
30 views

Probability of the same order

Let's consider a set $A$ and another set $B$ where $B \subset T$ . Conside another set $C= T \backslash B$(exclude set B from T). Now, We are given a stochastic process $X(t)$ such that $P(X(t)_{t \in ...
0
votes
3answers
18 views

Help with little-oh given $f(n) = n^\epsilon$ and $g(n) = (\lg n)^4$

Problem Given $f(n) = n^\epsilon, \epsilon > 0$ and $g(n) = (\lg n)^4$ find a little-oh relation between $f(n)$ and $g(n)$. Are $f(n)$ and $g(n)$ asymptotically different? Are they polynomially ...
0
votes
1answer
43 views

Asymptoting to 0: is erfc(z) quicker than exp(-z)?

If I have a function of the form $\mathrm{erfc}\left(z\right)/e^{-z}$, should I expect its limit at large $z$ to be $0$ or $\infty$? My instinct is that it should be $0$, by considering the ...
1
vote
0answers
37 views

Calculating Big O

I am reading a paper and cannot get through some technical proof regarding the calculation of big O). Below is the proof in that paper. Given two functions (CDF and PDF of a log-normal r.v.): $F(x) ...
1
vote
1answer
169 views

Do small o, small omega, and big theta cover all relationships between two functions

Given any two functions $f(n)$ and $g(n)$ is one of these three statements always true: $f(n) \in o(g(n))$ $f(n) \in \omega(g(n))$ $f(n) \in \Theta(g(n))$ Logically, this makes sense to me. For a ...
0
votes
0answers
14 views

Analogue of continuous mapping theorem

Suppose $X$ is a random variable defined on $[0,1]$ with probability density $f(x)$ for $x\in \mathbb{R}$. Based on a sample of size $n$, namely $X_1,\ldots,X_n,$ I defined an kernel estimator of ...
2
votes
4answers
89 views

Why does $\log(n!)$ and $\log(n^n)$ have the same big-O complexity?

In an example that I found, it is said that $\log(n!)$ has the same big-O complexity as $\log(n^n)$. Please explain why this is the case.
1
vote
0answers
23 views

The asymptotic behaviour of triples $n!+q^{n!}=c$, where $q$ is the first prime greater than $n$, and abc conjecture

For a large positive integer $n$, let $q=q(n)$ (below we denote this $q=q(n)$ by $q_{N}$ because we assumed that is the $N$-th prime number) the first prime number which is (strictly) greater that ...
2
votes
1answer
25 views

Big-O notaion for $2n^4 + \log_2n^8$

I need to find the best big-O for: $$3n^4 + \log_2n^8$$ So I said: $$3n^4 + \log_2n^8 = 3n^4 + 8\log_2n \leq 3n^4 + 8n$$ Therefore, the given function is $O(n^4)$ in the best case. Is this correct?
2
votes
2answers
28 views

Strong Induction to prove $T(n)$ is $O(n)$ for $T(n) = T(\lfloor n/3 \rfloor) + T(\lfloor n/5 \rfloor) + T(\lfloor n/7 \rfloor) + n$

I have some questions about Strong Induction where the inductive procedure isn't entirely clear to me. I will use a specific example to demonstrate and present my attempt at a proof with questions ...
0
votes
0answers
21 views

Asymptotic under logarithm [duplicate]

Suppose $f,g:\Bbb R\to \Bbb R$ are two functions such that $f(x)\sim g(x)$ for $x\to a$, that is $\lim_{x\to a}\frac{f(x)}{g(x)}=1$. Can we conclude that $$\log(f(x))\sim\log((g(x))?$$ Here is what ...
5
votes
3answers
232 views

How can I find $\lim_{n\to\infty}\int_0^\infty\frac{n\cos^2(x/n)}{n+x^4}dx$?

I am trying to find the value of this integral: $\displaystyle{\lim_{n\to\infty}\int_0^\infty\frac{n\cos^2(x/n)}{n+x^4}dx}$. The integrand tends to 1 as $n$ goes to infinity. So if some convergence ...
1
vote
0answers
31 views

Product of complex numbers $m+in$ with $0 < m,n \leq N$

I am trying to look for a generalization of Stirling's formula to complex numbers. In the integer case: $$ \log n! = \sum_{k = 1}^n \log k \approx \int_1^n \log x \, dx = n \log n - n$$ For the ...
-2
votes
1answer
34 views

What does θ(1) means in this equation?

Hello I am trying to understand this recurrence equation with no success. $ T(n) = T(n / 2) + θ(1)$ Base case : $T(1) = θ(1)$ and the solution is $θ(log_2 n)$. ...
1
vote
1answer
20 views

Is this true: $\frac{f(x)}{1-c-o(1)}= \frac{f(x)}{1-c}(1-o(1))$

Let $f$ be a function, for example $f(x)=log(1+x)$ and let $c$ be some constant $>0$ (for simplicity, we may assume that it is different from 1). Is this true: $$\frac{f(x)}{1-c-o(1)}= ...
1
vote
1answer
252 views

asymptotic behavior of the real part of the Riemann zeta function for $0<\sigma<1$

consider the zeta function $\zeta(\sigma+it)$ for $\sigma>1$ : $$\zeta(\sigma+it)=\sum_{n=1}^{\infty}\frac{1}{n^{\sigma+it}}$$ And: $$\zeta(\sigma-it)=\sum_{n=1}^{\infty}\frac{1}{n^{\sigma-it}}$$ ...
0
votes
3answers
67 views

Is there a simpler proof that $n^2 = O(2^n)$?

I am wondering if there is a simpler proof that $n^2 = O(2^n)$ which doesn't involve several layers of induction. My proof is as follows (sorry for the bad formatting). Proof: $n^2 = O(2^n)$ We will ...
1
vote
2answers
49 views

Behavior of transient states as $n \rightarrow \infty$

Let $(X_n)_{n \geq 0}$ be a discrete time-homogeneous Markov chain on the state space $E$. Suppose $T \subseteq E$ is the set of transient states. Can it be that we stay forever in $T$, with ...
0
votes
0answers
21 views

Compute asymptotic expansion of an integral along the unit circle

I want to compute the asymptotic expansion of the following integral with $t\rightarrow +\infty$ $\int_C\dfrac{(1+u)^{t+4}}{u^5}du$ where $C$ is the unit circle. I really appreciate your help. By ...
0
votes
2answers
27 views

Need help figuring out substitution with recurrence equation. [duplicate]

I need help with an Algorithm text book problem. The problem is the following T(n) = 2T(n/2) + n We guess that the solution is T (n) = O(n lg n). Our method is to prove that T (n) ≤ cn lg n for an ...
1
vote
0answers
90 views

The Big-$\mathcal{O}$ notation

Suppose that you take out a $\$15,000$ loan to purchase a car. The loan has an interest rate of $3\%$ per year, compounded monthly. The formula for the amount of interest accrued over a time period ...
-1
votes
2answers
47 views

Prove $\frac{1}{(1+z)^2}=1-2z + \mathcal{O}(z^2)$ as $z \to 0$ [closed]

Prove: $$\frac{1}{(1+z)^2}=1-2z+\mathcal{O}(z^2)$$ as $z\to 0$.
2
votes
0answers
41 views

Asymptotic conditional distribution of $\bar{Y}\mid\bar{X}=x$

I'm reviewing for my qualifying exam and I'm stuck on part of a problem. Setup Suppose that $(X,Y)$ are two random variables with joint distribution $ \begin{equation} ...
1
vote
1answer
16 views

Comparing Serveral Asymptotic Analysis Question

I have the following: $n^2\log(n)$, $2^n$, $2^{2^n}$, $n^{\log(n)}$, $n^2$. In increasing order, I think their order of growth is $n^{\log(n)}$ < $n^2$ < $n^2\log(n)$ < $2^n$ < $2^{2^n}$ ...