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

learn more… | top users | synonyms (1)

5
votes
3answers
123 views

Proof that $J_{\nu}(x) \sim (x/2)^\nu / \Gamma(\nu+1) \; \text{as} \; \nu \rightarrow \infty$

I'm working through the exercises of Bender and Orszag's famous book, but I got stuck in 6.25 (a), in which it is asked to prove that $$J_\nu (x) \sim (x/2)^\nu / \Gamma(\nu+1) \; \text{as} \; \nu ...
0
votes
0answers
17 views

Big-Oh for size of a Sperner family

I'm developing an algorithm that will generate a collection of subsets of a ground set having the property that no subset in the collection is a subset of any other, and I'd like to give a Big-Oh ...
5
votes
0answers
176 views

Summation of $1/(xy)$ over a triangular region

Let us consider a lattice formed by all points with integer and positive coordinates on a Cartesian plane, and where $K$ is the maximal value for the x-axis. Let us assign to each lattice point the ...
0
votes
0answers
40 views

Symbol of self-adjoint pseudodifferential operator

It seems that the following result should hold, but I can't find it explicitly anywhere. If $A=A^*$ is a properly supported pseudodifferential operator, does this imply that ...
1
vote
1answer
20 views

asymptotic behaviour of a product

Suppose $a_j\downarrow 0,b_j\downarrow 0$, and $a_j/b_j\rightarrow 1$. Do we always have $\prod_{j=1}^n\frac{1-a_j}{1-b_j}\rightarrow c$ as $n\rightarrow\infty$ for some finite constant $c$? Thanks!
0
votes
1answer
31 views

Asymptotic behaviour of a couple of special functions (features exponentials and logarithms)

I'm dealing with a couple of functions: $n \log n$, $( \log \log n)^{ \log n}$, $( \log n)^{ \log \log n}$, $n e^{\sqrt{n}}$, $( \log n)^{ \log n}$, $n 2^{ \log \log n}$, $n^{1+1/( \log \log ...
4
votes
1answer
50 views

On the sum of relatively prime number $<N$

Let $A(N)$ be a function which is the sum of all numbers relatively prime and $<N$ and $B(N)$ the sum of remaining $N−\phi(N)$ numbers. Then I have the following questions- Q-1 For what values of ...
12
votes
2answers
161 views

Convergence of power towers

Let's define the sequence $\{s_n\}$ recursively as $$s_1=\sqrt2,\ \ \ s_{n+1}=\sqrt2^{\,s_n}.$$ Or, in other words, $$s_n=\underbrace{\sqrt2^{\sqrt2^{\ .^{\ .^{\ .^{\sqrt2}}}}}}_{n\ \text{levels}}.$$ ...
1
vote
0answers
51 views

Prime Zeta Function

Does $$\sum_{p \text{ prime}} \frac{1}{p^s} \sim \log \zeta(s) \quad \text{as} \quad s \to 1^+$$ imply $$\sum_{p \leq n} \frac{1}{p} \sim \log H_n \quad \text{as} \quad n \to \infty,$$ where $H_n$ is ...
1
vote
1answer
40 views

Question about Big O Notation

I don't seem to understand big-O notation very well. If someone would explain it to me as well as explain how this problem would work Let f(n) = (3$^n$$^+$$^1$ - 3)/2. For each of the following ...
1
vote
1answer
37 views

Rearranging asymptotic notation

If $a \le b^{\frac{1+\log_{2}b}{2}}(1+o(1))$, then what is $b$ in terms of $a$? Whenever I try to rearrange this, I get in a huge mess... Any help would be appreciated. Thanks.
-2
votes
1answer
47 views

Prove that $\log n = O(\log^2 n)$

Trying to solve this, but I can't seem to figure it out. Its fairly straight forward.
1
vote
0answers
123 views

Limit of sequence of integral related i.i.d. observations

Let $X_1,\dots,X_n$ be i.i.d. random variables, each uniformly distributed on $[0,1]$. Let $\hat F_n$ be their modified empirical distribution function, i.e., $$ \hat ...
0
votes
1answer
17 views

Asymptotics of a bounded function

We have given a function $f(x)$ where we know that $f(x)\leq 1$ for all $x$. Is it true that $$1+O(f(x))=O(f(x))$$ even though I know that $1 \geq f(x)$? We know that $O(f(x))=o(g(x))$. Is it true ...
2
votes
2answers
55 views

Asymptotic approximation of binomial theorem

Binomial theorem is a very popular theorem that: $$(x + y) ^ n = \sum_{i=0}^n {n \choose i}x^i y^{n-i}$$ I am looking for any papers (the newer the better) where I can find any informations about ...
1
vote
1answer
30 views

Proving an asymptotic run time is faster than another using L’Hôpital’s

I'm working on a problem: Show using L’Hôpital’s Rule that a running time of $n\log(n)$ is asymptotically faster than (i.e., little-oh of) a running time of $\frac{n^2}{\log(n)}$.` I suppose a ...
2
votes
1answer
44 views

Prove or disprove a big o statement

I have to prove or disprove the following statement: $\forall a,b \in \mathbb{R}$, $b > 1$ : $n^a \in O(b^n)$ Clearly there are 2 cases: (i) $a < 0$ and (ii) $a \geq 0$, meaning that I have ...
1
vote
0answers
34 views

Simplify $\frac{n(k^2-1)}{2}$ to $ nk^2$

How does $\frac{n(k^2-1)}{2}$ become $nk^2$? I'm sorry for the stupid question but I'm at wits end and I have no idea how to go about this. Context Thanks
0
votes
1answer
43 views

Expected number of $k$-cliques in $G(n, 1/2) \ge 1$

Let the expected number of $k$-cliques be denoted by $$f(k) = \binom{n}{k} (\frac{1}{2})^{- \binom{k}{2}}$$ let $k_0$ denote the largest $k$ such that $f(k) \ge 1$. I want to prove that $k_0 = ...
4
votes
0answers
60 views

Looking for a closed form for the quotient of a sequence of compositions of $\exp()$-function

Related to that previous question I have another still open detail problem. Consider the sequence of evaluations at some given $x$ $$ \small \begin{array} {} z_0 &=& e^x \\ z_1 ...
1
vote
1answer
41 views

Which one of the following is greater?

Hi I am studying Asymptotic analysis but generally find difficulty in identifying the greater of two functions ? Like ex. $$f(n) = ((n^2)(\log_2(n))\\ g(n) = n((\log_2(n))^{10})$$ (here log are to ...
2
votes
2answers
49 views

Master theorem - why the log factor?

I think I finally managed to fully understand the master theorem but there's one thing left in the second clause (I'm following here: ...
1
vote
1answer
75 views

Order related to Empirical distribution function and Normal distribution

Let $X_1,\dots,X_n$ are i.i.d with distribution function $F$. Let $\hat F_n$ be its empirical distribution function, i.e., $$ \hat F_n(x)=\frac1n\sum_{i=1}^n1_{\{X_\le x\}}(x) $$ where $1_A(x)$ is the ...
4
votes
1answer
44 views

Problem understanding Master theorem

I'm studying the Master theorem (for the analysis of recursive algorithms) and I perfectly understand why a binary search is of order $\log_2(n)$. I also understand that if we formulate it as $T(n) ≤ ...
5
votes
0answers
95 views

What's the most efficient way to mow a lawn?

For $S\subseteq\Bbb R^2$ and $x\in\Bbb R$, define $E_x(S)=\{y\in\Bbb R^2:d(y,S)<x\}$. ($E_x(S)$ represents the expansion of $S$ by $x$.) Given a path $\gamma:[0,1]\to\Bbb R^2$, denote its length as ...
-2
votes
1answer
23 views

Simple question about big O

If $f(n)=g(n)$, can we just say that $\mathcal{O}(f(n))=\mathcal{O}(g(n))$? ($f$ and $g$ are two $\log$ functions) Is it definitely yes? if not please describe why.
2
votes
2answers
77 views

How to find the asymptotic behavior of this function

I have a function that I want to study it's asymptotic behavior. The function is $$ f(k) = - \frac{k^2}{4} - \frac{\log\pi}{2} + \log\left( \frac12 \left| \mathrm{Erfi}(\frac{k}{2} - \pi i) - ...
0
votes
0answers
20 views

What is the asymptotic bound of the recurrence : $T(n)= 2T\frac{n}{2}+\log n$?

I have managed to reach upto : $T(n) = 2.n.\log n - \log n - [2+2.2^2 +3.2^3 + \dots\log_2 n.2^{\log_2 n}]$ I m stuck here and not getting any clue how for solving the arithmetico-geometric series. ...
0
votes
0answers
44 views

Iterative Logarithm

For the iterative logarithm log log* n prove that it is a function of o(logk n) but also ω(1). For ω(1). I can prove that the function is ω(1) if I can show that log* n -> ...
3
votes
0answers
19 views

Computing the asymptotic spectrum of a negative distance kernel

Consider the following integral operator: $$K(f) : x \mapsto\int_0^1 K(x,x')f(x') dx', \quad \text{where} \quad K(x,x') = - |x-x'|^{3/2}.$$ The kernel is sometimes referred to as a negative ...
3
votes
2answers
69 views

Why is $\psi(x) = \sum_{n=1}^{\infty} e^{-\pi n^2x} = O(e^{-\pi x})$

We define $\psi(x) = \sum_{n=1}^{\infty} e^{-\pi n^2x}$. Why is it that $\psi(x) = O(e^{-\pi x})$ EDIT: As $ x \to \infty$ (big-oh-notation) I think we can assume that x is positive. I get that ...
0
votes
2answers
28 views

Multiplication of asymptotic approximation

If I know that: $a = (1 - O(\frac{1}{n}))$ and $b = (1 + O(\frac{1}{n}))$, what is the asymptotic approximation of $a\cdot b$? Is answer $ab = (1 - O(\frac{1}{n^2}))$ correct or it is still $ab = (1 - ...
4
votes
1answer
70 views

Applications of the Exponential Integral?

this is my first time asking a question on here so please forgive me if I have made any formatting mistakes. I have the integral $f(x) = \int_0^\infty \frac{e^{-t}}{x + t} \; dt$ and I have shown the ...
0
votes
1answer
30 views

Monotonicity of $f(x)-g(x)$ where $g$ is asymptotically greater than $f$

If $g(x) \succ f(x)$ (or $\lim_{x\rightarrow \infty}\frac{f(x)}{g(x)}=0$), will $g(x)-f(x)$ always be a strictly increasing function?
0
votes
2answers
267 views

How to arrange functions in increasing order of growth rate , providing f(n)=O(g(n))

Given the following functions i need to arrange them in increasing order of growth a) $2^{2^n}$ b) $2^{n^2}$ c) $n^2 \log n$ d) $n$ e) $n^{2^n}$ My first attempt was to plot the graphs but it didn't ...
0
votes
0answers
16 views

Can someone help me solve this recurrence using the Master Theorem?

Can someone help me solve this recurrence? $$T(n)= T(n^{1/2}) + Θ(\log\log n)$$ I know that I have to change the variables $m=\log n$. Then I have: $$S(m)=S(m/2)+Θ(\log m)$$ Case 2 of Master ...
2
votes
1answer
77 views

Asymptotic evaluation of integral method of steepest descent

The question asks to show that the leading term of the integral $$ \int_{-\infty}^\infty (1+t^2)^{-1}\exp\left(ik(t^5/5+t)\right) dt $$ for large $k$ using the method of steepest descent is equal to ...
1
vote
1answer
118 views

Infinite Series of the asymptotic expansion of Fresnel Integrals

I need to find the infinite series for the asymptotic expansions of the fresnel integrals as $x\rightarrow \infty$ and $x\rightarrow 0$. Now I have computed the asyptotic expansions to be as follows ...
1
vote
1answer
16 views

third order recurrence relation with non-constant coefficients

Does anyone know of a paper that may have been written on $3^{rd}$ order recurrence relations with polynomial coefficients, that is, one of the form $$A(n)a_{n+3}+B(n)a_{n+2}+C(n)a_{n+1}=D(n)a_n$$ ...
1
vote
2answers
43 views

Trouble understanding Big O notation for a sum of n integers [duplicate]

This problem is an example in a Discrete Math textbook. How can big-O notation be used to estimate the sum of the first n positive integers? Solution: Because each of the integers in the sum of the ...
1
vote
0answers
41 views

Evaluating a Limit with Generalized Harmonic Numbers.

Using WolframAlpha, I could informally come up with the following result: $$ \lim_{n \rightarrow \infty} \frac{H_n^{(-\frac{1}{2})}}{n\sqrt{n}} = \frac{2}{3} $$ Allowing me to infer that ...
0
votes
0answers
27 views

Determining the Asymptotic Order of Growth of the Generalized Harmonic Function?

How should I proceed to determine the order of growth of the generalized harmonic numbers? $$ H_{n}^{(r)} \in \mathcal{O}(?) $$
2
votes
0answers
39 views

Prove that (x+1)! is not O(x!)

Discrete math question which is as follows: Prove that (x+1)! is not O(x!) using only the definition of Big-Oh notation. (Hint!: log(a * b) = (log a + log b)) I used a proof by contradiction saying ...
1
vote
1answer
38 views

Is This Statement True?

Is it correct to assert that $T(n) \in \Theta(n^2)$ when: $$ \frac{n^2}{\log{(n)}} \leq T(n) \leq \frac{n^2}{\log{(n)}} + n $$
0
votes
1answer
23 views

General questions concerning asymptotic behavior

I have some difficulties understanding asymptotics in general. Is $O(n)$ the same as $O(-n)$? Is $O(f(n))$ the same as $O(cf(n))$ even though we know that $f(n)\leq 1$ for all $n$? I know the ...
1
vote
1answer
33 views

Power Iteration method for eigenvalues - Show the error is bound

Let $A \in $Sym$_{n}(\mathbb R)$ with eigenvalues $\lambda_i$ such that $|\lambda_1| > |\lambda_2| \geq |\lambda_3 |\geq ... \geq |\lambda_n|$ We define the following process as "Power Iteration": ...
1
vote
1answer
27 views

If $p(x)$ is a polynomial of degree d, prove that $p(x) \in \Theta(x^d)$

I just started learning asymptotic notation and I have a problem with this one. Let $p(x)=a_dx^d+a_{d-1}x^{d-1}+.....+a_1x+a_0$ be a polynomial of degree d, with $a_i \in \mathbb{R}$ for $0\leq i ...
2
votes
4answers
43 views

Why is $\log(n) \in o(\frac{n}{\log(n)})$?

This would be equal to: $\forall c>0: \exists n_0 \in \mathbb{N}: \forall n>n_0: c\log(n) ≤ \frac{n}{\log(n)}$ For $c=1$ this is obvious, because $\log(n) ≤ \sqrt{n} = \frac{n}{\sqrt{n}} ≤ ...
3
votes
1answer
35 views

Asymptotic approximation of a certain sum

During calculations of an expectation of some random variable, I have encountered the following sum: \begin{equation} \sum_{t=2}^{n+1} \frac{t(t-1) \cdot n!}{(n-t+1)!\cdot n^t} \end{equation} I ...
3
votes
2answers
48 views

Asymptotic behaviour of the number of sign changes in the sequence $\cos n\alpha$

Let $0$ $\leq$ $\alpha$ $\leq$ $\pi$. Denote by $V_n$$(\alpha)$ the number of sign changes in the sequence ${u_n}$ where $u_n$ $=$ $\displaystyle \cos n\alpha$. Then find the limit of the sequence ...