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
14 views

how to solve T(n)=T(Logn)+O(1)

Given That $T(1)=1$ Solve following recurrence function $T(n)=T(\log n)+O(1)$ I know the answer is $\log^* n$ but don't know how to prove it. What I tried: $\log(n)+\log(n-1)+\log(n-2)+...+1 = ...
0
votes
2answers
45 views

Does $O(\log^2(x))$ imply $O(x)$

Does $O(\log^2(x))$ imply $O(x)$ I have to prove the following: $$\sum\limits_{\substack{n\in\mathbb N\\n\le x}}\Lambda(n)\log(n)=\psi(x)\log(x)+O(x)$$ Applying partial sum I get; ...
0
votes
0answers
6 views

Deriving information about asymptotics from finitness of a limit

Let $f_1,f_2:\mathbb{R}\setminus\{0\}\to \mathbb{R^+}$ be two $C^1$ functions and $\alpha:\mathbb{R}\setminus \{0\}\to \mathbb{R}$ be a function from a Zygmund class (in particular it is Holder for ...
0
votes
0answers
16 views

How to solve asymptotic recurrence without using Master Theorem

I am working on the following problem. Consider the function $B:\mathbb{N}\to\mathbb{R}$ defined by: $$B(n) = \begin{cases} 1 & \text{if $n\leq 2$,}\\ 3\cdot B(\lceil n/\log_2 n\rceil) + n & ...
4
votes
1answer
47 views

Product of two sets with density zero has density zero?

Let $A$ and $B$ be two subsets of $\mathbb N$ which have asymptotic density zero. Define $A\times B$ as the set of integers of the form $ab$ with $a\in A$ and $b\in B$. Must $A \times B$ also have ...
0
votes
1answer
38 views

Why is $1 - \cos(x)$ of $\mathcal{O}(x^2)$?

I know the definition of order estimates, For the solution to apply we need to show: $ \displaystyle\lim_{x \to 0} \frac{1 - \cos(x)}{x^2} = A \neq 0\space or \space \infty$ But how can one show ...
4
votes
1answer
38 views

Order of Growth of a Sum

Let $n>k$ and $r$ be arbitrary positive integers. Define $q=k/n$. I want to show that $$ \sum_{i=0}^{rk} \binom{rn}{i}q^i(1-q)^{rn-i}(rk-i)=\Theta(\sqrt{r}) $$ as $r\rightarrow \infty$. I've ...
1
vote
2answers
12 views

Horizontal and Vertical Asymptotes of functions

So I'm completing a chart analyzing the different properties of three different functions: $f(x)=\log(x^2+6x+9), g(x)=\sqrt{x^2 -1}$ (sorry not sure how to do square roots on here), $h(x)=f(x)(g(x))$ ...
1
vote
1answer
31 views

Asymptotic of a complex integral

Consider the following integral $$f(x):=\int_x^{+\infty}re^{-(r+ir^2)}dr$$ I want to understand the asymptotic behavior of $f(x)$ as $x\rightarrow +\infty$ Thank you for any suggestion.
0
votes
1answer
87 views

Inverse of $x^x$ [duplicate]

Since $x^x$ grows very fast, its inverse should accordingly grow very slow, possibly slower than $\ln(\ln(x))$. I am troubled with finding such an inverse: I only get to the point: $\ln(x)x=\ln(y)$ ...
1
vote
1answer
53 views

Evaluate $\int_{x=0}^{\infty}\left(\frac{1}{\sqrt{x}}(1-e^{-x})\right)^{M-1}e^{-x}(1+sx)^{-N}dx,$

I am trying to evaluate $$\int_{x=0}^{\infty}\left(\frac{1}{\sqrt{x}}(1-e^{-x})\right)^{M-1}e^{-x}(1+sx)^{-N}dx,$$ where $s>0$, $M$ and $N$ are positive integers. But seem that the above integral ...
1
vote
3answers
61 views

Upperbound confusion

Why is the following true? $3n^2-100n+6$ is big $O$ of $n^2$ This has been demonstrated to be true when $c$ is $4$ and $n$ is $10$. $3*100-1000+6 = -694 = 694$ is the absolute value is a big $O$ of ...
2
votes
2answers
47 views

Large $a$ asymptotics of $\int_0^{\pi/4} \exp(-a(x^2-\frac{x^4}{3}))$

I'm looking for a way to prove that $\displaystyle \int_0^{\pi/4} \exp(-a(x^2-\frac{x^4}{3}))dx=\int_0^{\pi/4} \exp(-ax^2)dx+o\left(\int_0^{\pi/4} \exp(-ax^2)dx\right)$ as $a$ goes to $\infty$ ...
1
vote
0answers
25 views

Proof $\log(cn)$ is in $\Theta(\log(n))$

How can I prove that $\log(cn)$ is in $\Theta(\log(n))$, where $c$ is a constant? I tried to prove $c_1\log(n) \le \log(cn) \le c_2\log(n)$, where $c_1$ and $c_2$ are also constants, but I'm having ...
1
vote
3answers
36 views

Show that $\lim_{n\to\infty}\frac{n}{(\log n)^2}=\infty$

I am working on an asymptotic analysis question from a data structures past paper, and I need to show that $$\lim\limits_{n\to\infty}\frac{n}{(\log n)^2}=\infty$$ Could I have a hint for working out ...
0
votes
0answers
14 views

Expected size of largest connected component in a binary matrix

Let $C_4(\mathbf M)$ and $C_8(\mathbf M)$ denote the size of binary matrix $\mathbf M$'s largest 4-connected component and 8-connected component of the same value, respectively. For example, the ...
3
votes
1answer
62 views

A proof involving an infinite sum

I am trying to prove that there exist constants $C_1 > 0$, $C_2>0$ such that$$C_1 \log N \geq\sum_{k=1}^\infty(1 - (1- 1/2^k)^N) \geq C_2\log N$$ where $N\in Z^+$. Could you please give me ...
0
votes
2answers
36 views

Show that $\sin(\mathcal{o}(x)) = \mathcal{o}(x)$ as $ x\to 0$

So I want to show that $\sin(\mathcal{o}(x)) = \mathcal{o}(x)$ as $ x\to 0$. So far I have thought that my result will come from showing $ \displaystyle \Big|{\frac{\sin(f(x))}{x}}\Big| \to 0$ as ...
1
vote
3answers
44 views

$N^{1/2}$ and randomness

I apologize if this question is overly vague, but part of the reason I am asking is because I don't know a more precise way of discussing these ideas. To state a general question: What, if any, ...
2
votes
2answers
36 views

$\int_2^x\frac{dt}{\log^kt}=O\left(\frac{x}{\log^kx}\right)$

I seek to prove the identity $$\int_2^x\frac{dt}{\log^kt}=O\left(\frac{x}{\log^kx}\right)$$ I was given the following hint: Split the integral into $\int_2^{f(x)}+\int_{f(x)}^x$ for a ...
2
votes
2answers
23 views

Does one of these conditions on a sequence imply the other one?

Let ${(r_n)}_{n \geq 0}$ be a sequence of integers $\geq 2$. Set $q_n=\prod_{i=0}^{n-1} r_i$ (agreeing with $q_0=1$). I want to know whether one of these two conditions implies the other one (I think ...
1
vote
1answer
40 views

Compute $(\ln(n!))^2$

In a discrete mathematics past paper, I must solve the following problem: We know (from the Stirling approximation) that ...
1
vote
1answer
23 views

Asymptotics of $(\cosh(x+c)-\cosh(c))^{-\frac{1}{2}}$

let $c>0$ be a constant and consider the function $$\frac{1}{\sqrt{\cosh(x+c)-\cosh(c)}}, x>0.$$ I'm wondering how the asymptotic expansion for $x\downarrow 0$ look like!? In case of $c=0$ the ...
0
votes
0answers
11 views

Graphs Approaching Asymptotes

I've been wondering this for a while. For graphs that approach asymptotes, are there certain formulas that can determine the distance between the graph and the asymptote as $x$ gets infinitely small ...
1
vote
0answers
20 views

Approximation of Hermite functions

I'm looking for an "easy" proof of the asymptotic expansion of Hermite functions ($f_n(x)=H_n(x)e^{-x^2/2}$ where $H_n$ is the Hermite polynomials). The asymptotic expansion is $$ f_n(x) \sim_{n ...
0
votes
0answers
30 views

How to asses the order of combinations

Let $\{a_i\}_{i=1}^m$ be some increasing sequence, bounded away from zero. How to see that as $n\to\infty$, we obtain $$\begin{pmatrix} n\\ m \end{pmatrix}^{-1}\sum_{i=1}^m\begin{pmatrix} ...
1
vote
0answers
32 views

Two-term asymptotic approximation for roots of a polynomial (dominant balance)

I'm trying to find the roots to the following equation: $t^5 - \epsilon t^3 + \epsilon^3 = 0$ as $\epsilon \rightarrow 0$. From expansion $t= \epsilon^{\alpha}t_1 + \epsilon^{2\alpha}t_2 + ...
0
votes
1answer
13 views

$ n - \sqrt{n}$ $\Theta$ Complexity

$ n - \sqrt{n} \leq n - \sqrt{n} + \sqrt{n}=n=O(n)$ But I don't know what I should do about $\Omega(.) , \Theta(.)$ Should I try to solve it with lim?
0
votes
0answers
12 views

Additive error in Stirling's Approximation

I know that Stirling's Approximation is asymptotic to $n!$ as in the ratio approaches $1$ (which is the definition). But as far as I have noticed, the additive error diverges. Is this a common ...
3
votes
1answer
24 views

Trapezoidal Rule in Stirling's Approximation

https://en.wikipedia.org/wiki/Stirling's_approximation Here $$\sum \limits_{i=1}^n log(i) $$ is approximated as $$\int^n_1log(x) dx\ +\ 1/2\ log(n)$$ but I would approximate it as ...
5
votes
1answer
53 views

Decay of Fourier Transform

I encountered the following statement, and I cannot see why it is true(if it is). Suppose $f$ is a nonnegative, bounded, compactly supported and measurable function with the following properties: ...
7
votes
0answers
43 views

Decay of amplitude integral

Consider the function $$ f(\vec{x}) = \int_{\Bbb R^3} {\frac{ e^{-i\,\vec{x}\cdot\vec{k}}}{\sqrt{\vec{k}^2 + m^2}}} d^3 k $$ from Zee's Quantum Field Theory in a Nutshell. He argues like this: ...
0
votes
0answers
19 views

Node potentials of minimum cost flow successive shortest path algorithm

I have a simple directed graph $G(V,E)$ that has a source $s$ and sink $t$. Each edge $e$ of $G$ has positive integer capacity $c(e)$ and positive integer cost $a(e)$. I am trying to find the minimum ...
0
votes
0answers
22 views

Prove or provide a counter example: $f(n) \notin o(g(n))$ and $f(n) \notin \omega(g(n)) \implies f(n) \in \theta (g(n))$

$f(n) \notin o(g(n))$ and $f(n) \notin \omega(g(n)) \implies f(n) \in \theta (g(n))$ Without giving me the answer, please tell me how would you manipulate this? I know that $f(n) \in \theta (g(n)) ...
3
votes
2answers
41 views

Limit with polylog

How do you show the following limit? $$\lim_{x\to\infty} x\log(-e^x + 1)+\operatorname{Li}_2(e^x)-\frac12x^2=\frac{\pi^2}3$$ Where $\operatorname{Li}_n(x)$ is the polylogarithm. This question is ...
0
votes
0answers
32 views

Asymptotic analysis of Integrals of powers of sine and their application to intersections of hyperspheres

I am trying to estimate the probability of an event in an algorithm. For simplicity, assume there are two hyperspheres of radius $r$, at a distance $r$ from each other. I am looking to see how the ...
0
votes
1answer
23 views

comparing expressions confusion

This formula is actually from a big $O$ notation example, but I am confuse about the mathematical formula. I read that: if $n$ and $c$ are $1$, $3n^2 - 100n + 6$ is not a big o of $n^3$ or $cn^3 ...
2
votes
0answers
39 views

asymptotic expansion of hermite functions

Does anybody know how to proof the first asymptotic expansion of this page: http://en.wikipedia.org/wiki/Hermite_polynomials#Asymptotic_expansion ? (and how the physicist use this asymptotic ...
3
votes
1answer
89 views

$\sum \limits_{n \geq 0}a_n \frac{x^n}{n!}=e^{x+x^2/2}$ implies $a_n \sim \frac1{\sqrt2} n^{\frac n2}e^{ -\frac n2+\sqrt n -\frac14 }$

Prove the following asymptotic formula for the exponential generating function coefficients of $e^{x+x^2/2}$: $\; \; a_n \sim \frac1{\sqrt2} n^{\frac n2}e^{ -\frac n2+\sqrt n -\frac14 }$ Stanley ...
2
votes
2answers
33 views

is there a concept of asymptotically independent random variables variables?

To prove some results using a standard theorem I need my random variables to be i.i.d. However, my random variables are discrete uniforms emerging from a rank statistics, i.e. not independent: for ...
3
votes
3answers
64 views

Complete elliptic integral of the first kind $K(m)$ asymptotc expansion at $m = -\infty$

What is the asymptotic behavior of $K\left(-\frac{1}{\delta^2}\right), \delta > 0$ when $\delta$ tends to zero? Here $$ K(m) = \int\limits_0^{\pi/2} \frac{d\theta}{\sqrt{1 - m\sin^2 \theta}}, $$ ...
1
vote
2answers
31 views

Is this inductive big O proof possible / Does this question make sense?

Prove that $\sum_{i=j}^k \frac 1i$ is $O(\ln(k)-\ln(j-1))$ using induction for all $i$. The way I understand this question, it's nonsense - $i$ is the iteration variable, not something that can be ...
0
votes
2answers
22 views

Analysis of Algorithms - Big O Notation Equivalences - Limits

Please see below block question from review for test. True Or False? Justify Your answers A) is 2^(n+1) = O($2^n$) B) is 2^2n = O($2^n$) C) is log($n^2$) = O(logn) D) is ...
0
votes
0answers
8 views

WKB for a sixth order eigenvalue problem

I have the following 6th order eigenvalue problem: $$ (D^2 - \alpha^2)^3 y(x) = -\alpha^2 \lambda Q(x) \, y(x), \quad 0 < x < 1, \quad \text{+ BCs}, $$ where $D = \mathrm{d}/\mathrm{d} x $, ...
0
votes
0answers
29 views

Boundary layer problem

This question is taken from Bender & Orszag "perturbation methods" $y' = (1 + X^{-2}/100)y^2 - 2y + 1$ ,$y(1)=1$ first we can see that if we set $\epsilon=100x^{2}$ we can translate the above to ...
1
vote
1answer
35 views

Interpreting little-$o$ notation

This is the integrand of a complex integral: $$\frac{o(\zeta - z)}{\zeta - z}$$ The ensuing discussion says that this can be made as small as desired [by confining $\zeta$ close to $z$]. In general ...
3
votes
2answers
64 views

Question about steps/derivation regarding Laplace method.

I am reading something on the Laplace method of integrals and I don't understand part of it's argument. It gives the integral $$\int_{-3}^4 e^{-\lambda x^2}\log(1+x^2)dx$$ and finding the leading ...
3
votes
3answers
63 views

Wouldn't each addition take time $O(n)$?

I am going over the asymptotic runtime of regular matrix multiplication. Here is a lecture slide I am referencing(too much to type out, shown below), from Algorithms Everything makes sense up ...
1
vote
0answers
23 views

help with an asymptotic for a certain product

I'm having difficulty finding an asymptotic formula for the following product: $$ k^{\alpha}\prod_{1 \leq i \leq N \atop i \neq k} (i^{\alpha}-k^{\alpha})$$ where $N$ is a parameter tending to ...
0
votes
1answer
12 views

Asymptotic expansion for the inverse of a matrix-valued function

suppose I have an asymptotic expansion for a matrix-valued function $\psi : \mathbb{C} \to \mathbb{C}^{2 \times 2}$ : $$\psi(\lambda) \sim I + \frac{m_1}{\lambda} + \frac{m_2}{\lambda^2} + \cdots \ \ ...