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

learn more… | top users | synonyms (1)

2
votes
0answers
38 views

Asymptotic of a real double serie on $\mathbb{Z}$

I am interested by a real sequence $\{a_n\}_{n\in\mathbb{Z}}$ as $\sum_{n\in\mathbb{N}}\left(\vert a_n\vert + \vert a_{-n}\vert\right)$ converges. I want to find the asymptotic behavior of this ...
0
votes
0answers
10 views

random variables stochastically bound problem

Could you help me about stochastically bound problem for random variable. show that, there exist a sequence of {a_n} of positive real numbers such that X/a_n->0 a.s for any random variable X.
1
vote
0answers
11 views

Integral of product of Hermite functions with rescaled weights.

Let $$h_{k}(x)=c_{k}(-1)^k e^{\frac{x^2}{r^2}}\frac{d^k}{dx^k}e^{-\frac{x^2}{r^2}}$$ be the standard Hermite polynomials, rescaled with a given parameter $r>0$. The normalizing constant ...
3
votes
0answers
54 views

Verifying an integral identity related to asymptotic homogenization of an elliptic partial differential equation

Background I'm reading Hornung (1997)'s Homogenization and porous media, pg 3: We study a family of [1D] problems, indexed by the scale parameter $\epsilon=\frac{1}{n}$, namely, ...
1
vote
0answers
21 views

Proof that difference equations as asymptotic to their differential analog.

Given a difference equation $a_{n+k}=f(a_n,a_{n+1},\dots,a_{n+k-1})$, we can classify $n=\infty$ as an ordinary, regular singular, or irregular singular point by classifying $x= \infty$ in the ...
5
votes
2answers
75 views

How to show that $\sum_{x=1}^\infty \prod_{i=1}^{x-1} (1-i/n) \sim \sqrt{\frac{\pi n}{2}}$?

How can one show that asymptotically $$\sum_{x=1}^\infty \prod_{i=1}^{x-1} \left(1-\frac{i}{n}\right) \sim \sqrt{\frac{\pi n}{2}} \; ?$$ A non rigorous argument is to say that for large $n$, ...
0
votes
1answer
38 views

Big O - arithmetic rules

I need to prove the following statement: $O(f(n)g(n))=f(n)O(g(n))$ At first I thought the statement is false but apparently it is true. How can I prove it?
4
votes
1answer
70 views

How to show $\sum_{i=1}^{n-1} \frac{i(n-2)!}{(n-1-i)!n^{i+1}} \sim 1/n$

How can one compute the large $n$ asymptotics of $$\sum_{i=1}^{n-1} \frac{i(n-2)!}{(n-1-i)!n^{i+1}}\;?$$ My guess is that it is $1/n$ but I don't know how to show that.
0
votes
1answer
28 views

Big oh proof for a(n) using big oh hierarcy

So I'm given the following big-oh hierarchy (each sequence is big-oh of any seqeuence to its right.) $1$, $\log_2{n}$, ... , $\sqrt[4]{n}$, $\sqrt[3]{n}$, $\sqrt{n}$, $n\log_2{n}$, $n\sqrt{n}$, ...
4
votes
1answer
113 views

Growth of ratio based on sum of squared binomial identity

It is a well-known identity that $$\binom{n}{0}^2+\binom{n}{1}^2+\cdots+\binom{n}{n}^2=\binom{2n}{n}.$$ By symmetry of the binomial coefficients, this means the ratio ...
13
votes
5answers
984 views

Is there any nonconstant function that grows (at infinity) slower than all iterations of the (natural) logarithm?

Is there any nonconstant function that grows at infinity slower than all iterations of the (natural) logarithm?
1
vote
1answer
23 views

Asymptotic relation between specific binomial coefficient and exponential function

I need to determine the asymptotic relationship between the functions: $$f_1(n)={n\choose{\lfloor{n\over{2}}\rfloor}}, f_2(n)=7^{\sqrt{n}}$$ (I'm going to just assume $n$ is always even.) I've ...
1
vote
2answers
53 views

Finding an approximation for the difference of $a_n = \frac{1}{1+a_{n-1}}$ and it's limit.

I've got the recurrence $\displaystyle{a_{n} = {1 \over 1 + a_{n - {\tiny 1}}},\ }$ for $0 < a_{0} < 1 $ which has the solution $\displaystyle{\alpha = {\,\sqrt{\, 5\,}\, - 1 \over 2}}$ I am ...
0
votes
0answers
10 views

Asymptotics and function composition

In the following question: Big O and function composition It is explained that if $a, b, c, d$ are functions and $a = O(c), b = O(d)$ it doesn't mean that $a ∘ b = O(c∘d)$. However, what if we allow ...
5
votes
2answers
364 views

Inverse of sparse matrix is not generally sparse

I have a question regarding inverse of square sparse matrices(or can be restricted to real symmetric positive definite matrices). I encountered several times the web pages which states that the ...
0
votes
0answers
9 views

GRAM series and Logarithmic integral

due to the prime number theorem wouldn't we expect that the prime number counting function admits the approxiamtion $$ \pi (x)= \gamma +loglog(x)+ \sum_{n=1}^{\infty} \frac{log^{n}(x)}{n.n!.\zeta ...
2
votes
1answer
53 views

Number of words not having a subword of length k with only one letter

Let $f_k(n,t)$ be the number of words of length $t$ over the alphabet $\mathcal{A} = \{1,\ldots,n\}$ such that no word contains $i^k$ as a substring for $i \in \mathcal{A}.$ I am looking to find the ...
1
vote
0answers
34 views

Order of magnitudes comparisons

I need your help with the following. I need to determine how to order (functions) the following : \begin{align} &f(x)=(x/2)^{(x/2)} \\ &g(x)=x! \end{align} Note: I got both of them are ...
0
votes
0answers
34 views

Big-O Notation Division

There was a similar thread on this question, but I am still unsure about the answer. I am asked to show, $$ \frac{e^{(r-q)h}-e^{-\sigma\sqrt{h}}}{e^{\sigma\sqrt{h}}-e^{-\sigma\sqrt{h}}} = ...
6
votes
1answer
353 views

Evaluating a limit of the truncated exponential series motivated by the prime number theorem for $k$ distinct prime factors.

If $\pi_k(n)$ is the cardinality of numbers with k factors (repetitions included) less than or equal n, the generalized Prime Number Theorem is: $$\pi_k(n)\sim \frac{n}{\ln n} \frac{(\ln \ln ...
2
votes
1answer
83 views

Corollaries of Green-Tao Theorem?

there is already a good thread which discusses some corollaries of the Green-Tao Theorem, here: Constructing arithmetic progressions The question I was wondering about is of a similar flavor but ...
0
votes
0answers
35 views

Sort functions by their growth rate

So yesterday I had a mock exam and I failed an exercise. I'm trying to solve it but I definitely can't reach the solution. Here's the problem : Arrange the following functions in a list, so that ...
-1
votes
1answer
22 views

big $\Theta$ question dealing with $\log_2{n}$ and $\log_{10}{n}$

Show that $\log_{10}{n} = \Theta(log_2{n})$. I know that I have to show that 1) $\log_{10}{n} = O(\log_2{n})$ show: $\log_{10}{n} \le C * \log_2{n}$ and 2) $\log_2{n} = O(\log_{10}{n})$ show: ...
0
votes
0answers
16 views

Big theta question

Find a number $a$ with $s(n) = \Theta(a^n)$ for $s(n) = 1^{(n^2+200n+5)}$. I worked out that $a = 1$ and that $1^{(n^2+200n+5)} \le C * 1^n, C = 1, n = 0.$ So long as n $\ge$ 0 the right-hand side ...
0
votes
1answer
19 views

Big oh / big theta proof for the following

Find a number $a$ with $s(n) = \Theta(a^n)$ for $s(n) = (\log_2{10})^{(n-3)}$. I'm not quite sure how to proceed. I was having problems with another problem trying to figure out what it means to ...
0
votes
2answers
43 views

Why is Wolfram missing so many oblique asymptotes? (Not only about Wolfram in thread)

Few days ago I made a post, and to be frank I'm not sure if I'm even having this question in the right forum. But I'm also looking for information on if my thoughts are correct. Observe this little ...
0
votes
1answer
34 views

Proving big oh for a function

Find a $C$ and $k$ such that $\sqrt{n^2 - 1}$ = $O(n^k)$. My professor has stated that there are two different $k$'s. One from the problem statement and one from the definition of big-oh. I know that ...
0
votes
3answers
59 views

Finding the limit of: $\lim_{x\rightarrow +\infty}\left(x\arctan x-x\dfrac{\pi}{2}\right)$

$\lim_{x\rightarrow +\infty}\left(x\arctan x-x\dfrac{\pi}{2}\right)$ I just removed a lot of unnecessary text from this post. If anyone could tell me how to find this limit, without L'Hôpital's rule, ...
1
vote
2answers
86 views

Find the leading order asymptotic behaviour of the integral

$$I(x) = \int_0^{\infty}e^{-t-\frac{x}{t^2}}dt \mbox{ as } x \mbox{ tends to infinity} $$ I know this has a moveable maximum so you need to make a substitution which transforms it into the integral: ...
3
votes
1answer
23 views

Oblique asymptote for: $f(t) = \frac{t^2\arctan t}{t-4}$?

Say a function $$f(t) = \frac{t^2\arctan t}{t-4}$$ Obviously, this has a vertical asymptote at $t = 4$. However, the oblique asymptote, if there is one, I can't seem to find. What I do is I put the ...
1
vote
1answer
40 views

Calculate the leading order asymptotic behaviour (with two maxima)

thanks in advance! Calculate the leading-order asymptotic behaviour of the integral $$I(x) = \int_{0}^{2\pi} (1+t^2) e^{x \cos t} dt \mbox{ as } x \mbox { tends to infinity}$$ So far I know there ...
1
vote
1answer
38 views

Asymptotic solution to a differential equation near zero

I am trying to get the both the asymptotic solutions of the equation $y''(x)=\sqrt{x} \cdot y(x)$ as $x\rightarrow 0$. But when I put $y(x)=\exp(S(x))$ since $x=0$ is an irregular singular point, no ...
0
votes
1answer
22 views

How to prove this asymptotic bound? [closed]

Given that $0<a<b$, $f(n) \in O(n^a)$, prove that $f(n) \in o(n^b)$ (note there is a difference between big o and little o)
0
votes
0answers
12 views

Determining if f(n) is Big-O of g(n)

I'm currently learning Big-O notation but I'm having a lot of trouble understanding it. I'm working through some true/false exercises: 1) $log(k)$ is $O(k)$ 2) $klog(k)$ is $O(k^2)$ 3) $k^2$ is ...
2
votes
0answers
24 views

Number of ways to visit each cell of $n\times n$ board once

A piece lies on the upper-left corner of an $n\times n$ board. Let $f(n)$ denote the number of ways to move the pieces one step horizontally/vertically at a time, so that it visits each field of the ...
1
vote
3answers
61 views

Iterated integer-valued decimation

This question is for those who have wondered what it means to decimate an army when the number of soldiers is not a multiple of ten. I am interested in really good upper bounds on the length of a ...
0
votes
1answer
27 views

Lower bounds for an expression of two positive integers?

Can we get an approximate lower bounds for the following expression: $$\left( 1 + \frac{1}{ 2 \left( \frac{4^{nC}-1}{2^n-1} \right) } \right)^{ \frac{1}{\left( \frac{4^{nC}-2^{nC}}{2^n-1} \right) } ...
2
votes
1answer
37 views

Asymptotics of $\frac{1}{n} \sum_{ d|n } \mu{\left(\frac{n}{d}\right)} 2^d $

Define $$a(n) = \frac{1}{n} \sum_{ d|n } \mu{\left(\frac{n}{d}\right)} 2^d $$ where $\mu()$ is the Möbius function. Is it possible to find easily computable $b, c$ such that $b(n) \leq a(n) \leq ...
0
votes
2answers
39 views

Show that $3n^2 - n+4$ is $O(n^2)$

From the definition of big oh: We say that "$f(n)$ is big oh $g(n)$" if there exists an integer $n_0$ and a constant $c>0$ such that for all integers $n\geq n_0$, $f(n)\leq cg(n)$. Substituting ...
0
votes
1answer
88 views

Proof of simple relation involving near primes?

Motivation (can skip!). (*) $\sum\log n \approx n\log n-n,$ and $$\sum\log n = \sum_{p_1\leq n} \log p_1+\sum_{p_2\leq n} \log p_2+...+\sum_{p_m\leq n} \log p_m$$ in which $p_k$ are numbers comprised ...
1
vote
0answers
26 views

Calculate the leading-order asymptotic behaviour (Laplace's Method) [duplicate]

thanks in advance! Calculate the leading-order asymptotic behaviour of the integral $$I(x) = \int_{0}^{2\pi} (1+t^2) e^{x \cos t} dt \mbox{ as } x \mbox { tends to infinity}$$ So far I know there ...
0
votes
2answers
15 views

Determine the asymptotic behavior of $f(n)$ in relation to $g(n)$

$f(n)=n^\sqrt{n}, g(n)=2^n$ $f(n)=10^{\log\log n}, g(n)=\log n$ Note: $\log$ is in base 2. For section #1, I tried to evaluate the limit $\lim_{n\to\infty} \frac{2^n}{n^\sqrt{n}}$ but got stuck ...
1
vote
0answers
24 views

How to prove that a function f(x) is O(g(x)), using the definition (finding C and k)

We say that $f(x)$ is $O(g(x))$ if $$(∃C ∈ \mathbb(R)❘)(∃k ∈ \mathbb(R)❘)(∀x ∈ \mathbb(R)❘)$$ $$(x ≥ k → |f(x)| ≤ C · |g(x)|)$$ In English: We can find $C$ and $k$ so that, once we get past the “small ...
0
votes
0answers
27 views

Am I to place my trust in Wolfram on this matter? [Oblique asymptotes on a function]

So I used Wolfram to find oblique asymptotes for the following function $f(x) = 2x + 3 - \frac{1}{\ln x}$ The vertical asymptote, which Wolfram finds as well, is $x=1$. However, my method for finding ...
2
votes
3answers
429 views

big O notation with asymptotically nonnegative increasing functions

Let $f(n)$ and $g(n)$ be asymptotically nonnegative increasing functions. Show: $f(n) · g(n) = O((\max\{f(n), g(n)\})^2)$, using the definition of big-oh. I can't quite figure this out, can ...
1
vote
1answer
85 views

Find asymptotics in a given form $n=(e+o(1))^{f(s)}$

Let $p\to\infty$, $s={\binom {p^4} p}$ and $n={\binom {p^4}{p^2}}$. Find a function $f(s)$ in the following form $$\large n=(e+o(1))^{f(s)}$$ I've tried to use the followinf asymptotics for ...
0
votes
1answer
39 views

Disproving a relation between function and derivative concerning Big-O-Notation

The question is to disprove the following: Be $f$ a continuously differentiable function that maps from $\mathbb{R}\rightarrow\mathbb{R}$ and $f(x) =\mathcal{O}(x^2) $ for $x\rightarrow0$, then it ...
0
votes
1answer
58 views

$\frac{a_n - a_{n+1}}{a_n} \approx \frac{1}{n}$? (part of 2010 Putnam exam)

Given a non-negative sequence $a_n$, strictly decreasing and tending to zero, can we show that (for large $n$) $$ \frac{a_n - a_{n+1}}{a_n} \approx \frac{a_n}{na_n} = \frac{1}{n} \text{ }?$$ ...
1
vote
2answers
65 views

Solving $T(n)= 2T(n/2) + \sqrt{n}$ without master theorem (algebraically & recurrence tree)

$$T(n)= 2T(n/2) + \sqrt{n}$$ This recurrence was in a stackoverflow question, and I want to solve it without relying on the master method. The solution was given, but wolframAlpha gives a slightly ...
2
votes
1answer
38 views

Finding an upperbound on $f(n)$

I am stumped trying to prove that there exists a real number $c$, such that $f(n)\leq cn^4$ for most natural numbers $n$. $$f(n) = \left\{ \begin{array}{ll} 10, &n=10\\ ...