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

learn more… | top users | synonyms (1)

1
vote
1answer
50 views

What does the symbol <<< mean? [duplicate]

Can anyone give the LaTeX code for the unusual symbol <<<, and perhaps provide some good examples of its use? Does it mean "much much less than"?
2
votes
0answers
21 views

Upper bound for $|\zeta'(s)|$ near the line $\sigma=1$, a detailed proof

In page 285 Apostol leaves as a reader's asigment the proof that $|\zeta'(s)|=O(\log^{2}t)$, this is for every $T>0$ there exists a positive constant $K$ (depending on T) such that ...
2
votes
2answers
570 views

How to recognise intuitively which functions grow faster asymptotically?

There are some cases where it is not so simple to decide which function grows faster asymptotically. For example, in the following cases, why (intuitively) $g(n)$ should grow faster than $f(n)$, or ...
0
votes
0answers
16 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
21 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
26 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
72 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
70 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
34 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
90 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
79 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
46 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
45 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
50 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 ...
4
votes
2answers
62 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
67 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
37 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
36 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
15 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
44 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
54 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 ...