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
0answers
11 views

Proof verification regarding asymptotics

Prove $f(z)=o(\phi (z))$ implies $f(z)=O(\phi (z))$ as $ z \to 0$. My proof is: The assumed statement is $$\lim_{z \to 0} \frac{ f(z)}{\phi (z)}=0$$ That statement implies the function $\frac{ ...
2
votes
0answers
20 views

A modified Shapiro's Tauberian theorem? Proof or counterexample

Let $\{a(n)\}$ be a nonnegative sequence such that $$\sum_{n\leq x}a(n)[x/n^{2}]=x^{2}\log x + O(x^{2})$$ for all $x\geq 1$, where $[y]$ denotes the greatest integer $\leq y$. Is true that the ...
0
votes
0answers
25 views

Distribution of the test statistic?

Let $\mathbf{x}_i \sim \mathcal{N}(\boldsymbol\mu, \boldsymbol\Sigma)$. I am trying to find a distribution of the following test statistic $ T(\mathbf{x}) = \frac{\bar{\mathbf{x}}^H ...
5
votes
4answers
68 views

Asymptotic of Inverse Function

Suppose we choose a positive constant $c$ and let $f_c(x)=\frac12x^2+cx^{3/2}$. I would like to get an asymptotic estimate for the function $f_c^{-1}(x)$ as $x\rightarrow\infty$. I assume it will be ...
6
votes
1answer
64 views

Analytical approximation of integral of Bessel function

I am trying to approximate the integral: $$ \int_0^z \left(\frac{J_1(x\,\sin\theta)}{\sin\theta}\right)^2 {\rm d}\theta $$ My very naive approach was to do the Taylor series of the integrand. ...
0
votes
0answers
12 views

What does “empirical error” mean in this context?

I recently sat an exam for computational mathematics. The question asked for us to: "Write the empirical error in $\mathcal{O}(n^{-p})$ where $p$ is some integer" We were given a series $$S = 4(1 - ...
0
votes
1answer
37 views

What does it mean to say $f(x) \sim g(x)$, i.e. $f(x)$ behaves like $g(x)$ when $x \to \infty$?

If $\lim_{x\to\infty}\frac{f(x)}{g(x)}=\infty$, then $f$ grows faster than $g$. Same if $\lim_{x\to\infty} \frac{g(x)}{f(x)} = 0$. Would $f$ behave like $g$ if $\lim_{x\to\infty}\frac{f(x)}{g(x)} = ...
1
vote
1answer
33 views

Asymptotic Estimates for a Strange Sequence

Let $a_0=1$. For each positive integer $i$, let $a_i=a_{i-1}+b_i$, where $b_i$ is the smallest element of the set $\{a_0,a_1,\ldots,a_{i-1}\}$ that is at least $i$. The sequence ...
0
votes
2answers
16 views

$T(n) = 3T(n/3) + c$ using substitution, geometric series

so I have to find the asymptotic complexity of $T(n) = 3Tn(n/3) + c$ using either the substitution method, a recursion tree or induction. I used the Master Theorem to find an answer, but can't use ...
10
votes
0answers
89 views

Asymptotic Behavior of a Sum with Binomial Coefficients

The Problem: Find the asymptotic behavior (with respect to $n$) of the following sum $$\sum\limits_{j = 3}^n \binom{n}{j} \frac{(j - 1)!}{2\cdot n^j}. $$ Where the Problem Comes From: If we ...
3
votes
1answer
76 views

Can I find a good approximation of this function?

I am wondering, if I can find a good approximant for this function $$f(z)=\log \left[ \frac{1-z^2}{z \left(3-z^2\right)}\sinh \left\{\frac{z \left(3-z^2\right)}{1-z^2}\right\}\right]$$ assuming $z ...
2
votes
2answers
45 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 ...
1
vote
2answers
44 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
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
48 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 ...
2
votes
0answers
35 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 ...
1
vote
1answer
39 views
+50

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 ...
0
votes
2answers
34 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, ...
1
vote
1answer
65 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 ...
2
votes
2answers
89 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 fixed positive integer ($m>1)$ 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 $ as $ n ...
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
24 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 ...
3
votes
0answers
36 views

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
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
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
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 ...
0
votes
2answers
35 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 ...
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 ...
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) - ...
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
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 ...
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) ...
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
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 ...
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
1answer
51 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
0answers
26 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
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.
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
30 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 ...
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)}= ...
0
votes
3answers
68 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
51 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 ...