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
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
17 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
28 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 ...
1
vote
1answer
45 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 ...
5
votes
0answers
101 views

Asymptotic expansion of $\zeta(s)$

It is well known that $$ \zeta(s) = \sum_{n = 1}^\infty \frac{1}{n^s} = \prod_{p \text{ prime}} \frac{1}{1 - p^{-s}}, \quad \Re[s] > 1, \tag{1}$$ but, if $p \leq N$ denotes the primes less than or ...
-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
1answer
35 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
2answers
71 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) - ...
2
votes
2answers
50 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 ...
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
1answer
42 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
41 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 = ...
1
vote
1answer
40 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 ...
7
votes
6answers
893 views

Which one is bigger $2^{n!}$ or $(2^{n})!$?

Which one is bigger $2^{n!}$ or $(2^{n})!$ ? where $n\in\mathbb N$.
4
votes
0answers
58 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 ...
11
votes
1answer
93 views

Expected values of some properties of the convex hull of a random set of points

$N$ points are selected in a uniformly distributed random way in a disk of the unit radius. Let $P(N)$ and $A(N)$ denote the expected perimeter and the expected area of their convex hull. For what ...
2
votes
2answers
46 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: ...
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 ...
1
vote
1answer
73 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
3answers
227 views

Asymptotic expansion of $J(t) = \int^{\infty}_{0}{\exp(-t(x + 4/(x+1)))}\, dx$

I want to derive an asymptotic expansion for the following Bessel function. I think I need to rewrite it in another form, from which I can integrate it by parts. I am interested in obtaining the ...
4
votes
1answer
43 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
90 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
22 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.
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 -> ...
0
votes
0answers
19 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. ...
1
vote
1answer
106 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 ...
3
votes
0answers
17 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
64 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
27 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 - ...
19
votes
7answers
1k views

Is there a formula for $\sum_{n=1}^{k} \frac1{n^3}$?

I am searching for the value of $$\sum_{n=k+1}^{\infty} \frac1{n^3} \stackrel{?}{=} \sum_{n = 1}^{\infty} \frac1{n^3} - \sum_{n=1}^{k} \frac1{n^3} = \zeta(3) - \sum_{n=1}^{k} \frac1{n^3}$$ For which ...
2
votes
1answer
70 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 ...
0
votes
2answers
195 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 ...
4
votes
1answer
67 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 ...
1
vote
0answers
39 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
1answer
114 views

Big O Notation Exercise

I'm having a small problem. I'm very new in this section so please bear with me. I understand Big O meaning what everything signifies like the $O(n), O(n^2), O(x^n), O(\log n)$ and $O(1)$. I also ...
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?
10
votes
2answers
440 views

How prove this sequence $a_{n}=\sqrt{n}+\frac{1}{2}-\frac{1}{8\sqrt{n}}+o\left(\frac{1}{\sqrt{n}}\right)?$

let sequence $\{a_{n}\}$ such $$a_{1}=1,a_{n+1}=1+\dfrac{n}{a_{n}}$$ show that: $$a_{n}=\sqrt{n}+\dfrac{1}{2}-\dfrac{1}{8\sqrt{n}}+o\left(\dfrac{1}{\sqrt{n}}\right)?$$ This result is china student ...
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$$ ...
4
votes
1answer
47 views

How to find the sum of Big-Oh's?

I will admit this is a homework problem, but I'm seriously stuck. I'm not looking for answers, but just any hints as to what to do next. Any tips would be appreciated. I am given: $$f_1(x) = ...
1
vote
0answers
42 views

Computational Complexity

My question is very basic, it is just so that I have a basic grasp of the terminology of algorithm speed. When someone says an algorithm speed is $O(n^2)$ they say that the number of steps of this ...
1
vote
2answers
39 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 ...
0
votes
0answers
25 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
38 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
92 views

Asymptotics of sum of Binomial Coefficients (Binomial distribution) - Poisson approximation?

Let $$f(n):=\sum_{i=k}^n {n \choose i } p^i (1-p)^{n-i}$$ where $k\geq 2$ is a fixed Parameter and $p=p(n) \in (0,1]$ depends on $n$ where $np\leq 1$. We consider $n \rightarrow \infty$. I've found ...
1
vote
1answer
37 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 $$
1
vote
1answer
30 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": ...
0
votes
1answer
22 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
24 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 ...