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

Question about your function,

I'm Xavier Vigan, a physical oceanographer. I've been using your $f(x)=\dfrac 12 \times \left(X+C-\sqrt{S+(X-C)^2}\right)$ function to calibrate quantile vs quantile plots. Because of the shape of ...
0
votes
0answers
20 views

Finding the asymptotic expansion of $\sin(3x)$ using asymptotic sequence $\{\ln(1+x^n)\}_n$

Finding the asymptotic expansion of $\sin(3x)$ using asymptotic sequence $\{\ln(1+x^n)\}_n$. In the notes and lectures the only example that was given was an expansion for $\tan(x)$ where she ...
1
vote
0answers
7 views

Optimizing an asymptotic recurrence relation with two recursive terms

I have a recurrence relation that looks like this: $T(n) = 2 T(c n) + T((1-c)n) + O(n)$ The base case is just $T(b) = 1$ when $b \leq 1$. I'm trying to figure out the best value of $c \in (0, 1)$ ...
0
votes
4answers
42 views

Big-O notation — is it mainly used to classify rate of growth or rate of decay to zero?

For example, $e^{x} = 1 + x + x^2/2 + O(x^3)$, and we interpret $O(x^3)$ as the remainder term that goes to zero like $x^3$. What's the primary usage of Big-O notation? (strictly in math classes, ...
0
votes
3answers
23 views

relationship between Big $O$ notation and limit

If I have a function $f(n)$ such that $f(n) \geq 0$ for all positive integers $n$ and that $\lim\limits_{n\to \infty} f(n) = 0$, then can I conclude that $f(n) = O\left( \dfrac{1}{n^k}\right)$ for ...
0
votes
2answers
38 views
3
votes
1answer
49 views

length of the curve $y=x^n$ in the unit square

Let $l_n$ be the length of the curve $y=x^n$ in $[0,1]\times[0,1]$. Then obviously $\lim_{n\to\infty}l_n = 2$. What about $\lim_{n\to\infty}(n(2-l_n))$ ? The formula $l_n = ...
0
votes
1answer
35 views

can use diagonal matrix in a formula to figure out how many characters would occur in all substrings of a string 's'?

Math experts - I'm working through a simple "big O" analysis of algorithms problem comparing two approaches to the longest substring problem. One approach is brute force: checking all possible ...
0
votes
1answer
22 views

Little o notation within another little o

To prove $e^{x + o (x)} = 1 + x$ as $x \rightarrow 0$, I can do it directly: $\lim_{x \rightarrow 0} \frac{\log (1 + x) - x}{x} \overset{\text{l'hopital}}{=}\lim_{x \rightarrow 0} \frac{(1 + x)^{- ...
3
votes
1answer
38 views

Density of linear combination

Let $r_1, \ldots, r_n$ be a set of positive reals. Define \begin{equation*} S = \{a_1r_1+\cdots+a_nr_n : a_i\in \mathbb{N}\}. \end{equation*} Define $\pi(x)= |\{a\in S:a<x\}|$. Is there an ...
2
votes
0answers
24 views

WKB leading order

I'm learning about the WKB method, and I'm applying it to an assignment. The assignment question asks to find the "leading order" WKB expansion for the particular equation. For WKB you make the ...
0
votes
0answers
27 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 = ...
1
vote
2answers
60 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
8 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
52 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
39 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
14 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))$ ...
2
votes
1answer
35 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
91 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
54 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
26 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
71 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
45 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
24 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
31 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
13 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
25 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
54 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
45 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
23 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
26 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
33 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 ...