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

learn more… | top users | synonyms (1)

6
votes
1answer
74 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
33 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 ...
9
votes
2answers
8k views

Quicksort Running Time

I am trying to refresh my knowledge (and hopefully learn more) about Algorithm Analysis. I took a course on this two years ago but I am trying to catch up on what I had learned back then. The way I ...
1
vote
0answers
13 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
39 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)} = ...
8
votes
5answers
194 views

The maximal size of between $\varphi(n)$ divided by $\lambda(n)$.

I want to find $$f(n) = \max\left\{\frac{\varphi(k)}{\lambda(k)} : 1 \leq k \leq n\right\}$$ In other words, I want to find the maximal value of $\frac{\varphi(k)}{\lambda(k)}$ when $k$ is ...
0
votes
2answers
18 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 ...
1
vote
0answers
22 views

Does an exponential bound on a Lyapunov candidate imply asymptotic stability?

If I have a Lyapunov candidate $V:[0,\infty)\rightarrow \mathbb{R}$ and I'm able to show that $$ V(t)\le k e^{-\eta t} V(0),\qquad \forall t\in[0,\infty) $$ can I conclude something about ...
3
votes
1answer
83 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
53 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
495 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 ...
1
vote
2answers
48 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
33 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
53 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
40 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
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, ...
3
votes
0answers
41 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
0answers
16 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
57 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
31 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

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
61 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 ...
1
vote
2answers
32 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
91 views

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
52 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
29 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$.
2
votes
0answers
26 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
17 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
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 ...
1
vote
0answers
38 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
190 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
16 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
3answers
101 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
27 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
32 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
32 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
35 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
261 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
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
52 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
22 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
29 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 ...