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
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
52 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
94 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
74 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
237 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
76 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
114 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
41 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
40 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
33 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 ...
0
votes
1answer
61 views

How many self-complementary graphs are there of a given size?

How many self-complementary simple graphs are there on $n$ vertices, up to isomorphism? Denoting this by $S(n)$, it is clear that $S(n)=0$ unless $|K_n|=\frac{n(n-1)}2$ is even, which is when $n=4k$ ...
0
votes
1answer
47 views

Is this Asymptotic Statement true?

Is this statement true? If so, how can I prove it? If not, why not? $$ \frac{n^2}{\log{(n)}} \in \Theta(n^2) $$ Recall the definition of Big Theta asymptotic notation: $f(n) \in \Theta(g(n))$ means ...
1
vote
1answer
32 views

Why does the asymptotic equation of the modified Bessel of the second kind (Iv) have an imaginary part?

This is a follow up to this question. How does one arrive at the asymptotic expressions for the bessel functions? After looking at: G. N. Watson, "A Treatise on the Theory of Bessel Functions", 2nd ...
0
votes
1answer
10 views

A question on an asymptotic combinatorial expasion

Suppose we are given $(\lambda a + \bar{\lambda}b+O(\lambda^2))^{n}$, where $0 < \lambda < 1$ and $\bar{\lambda} := 1-\lambda$; also, $0 < a,b < 1$. $O(\cdot)$ is the traditional Big-Oh ...
1
vote
1answer
44 views

Given a set $S$, find any $N$ numbers than sum to $X$

Similar but different from the problem here. I have an unsorted set $S$ of real numbers, and need to sum elements from $S$ to find the real number $X$; However, It could be from $1$ to $N$ elements ...
1
vote
1answer
98 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 ...
2
votes
1answer
43 views

Source needed: Does asymptotic normality yield asymptotic unbiasedness and consistency?

Assume that $$\sqrt{n}(\hat g - g(\theta)) \xrightarrow{d} Z, $$ where $Z$ is $N(0,\sigma^2)$. Does this already imply asymptotic unbiasedness and/or consistency, i.e., $$ E[\hat g] \rightarrow ...
1
vote
1answer
46 views

Asymptotic behavior of $\pi (x)-\frac{x}{\log x}$

What is the asymptotic behavior of the function given below. $$f(x)=\pi (x)-\frac{x}{\log x}$$ $$f(x)=O(g(x))$$ What can be $g(x)$? Also what is the asymptotic behavior of the $h(x)=f(x)-g(x)$. My ...
1
vote
2answers
72 views

How does one arrive at the asymptotic expressions for the bessel functions?

It is known that Bessel functions for large arguments will behave as exp or cos/sin however I was wondering how does one arrive at those results. The motivation being that I would like to use these ...
4
votes
2answers
104 views

What does this $\asymp$ symbol mean? (subject: analytic number theory)

I'm reading a survey article by Andrew Granville on analytic number theory. On page 22 of the paper, there appears a strange looking symbol, undefined. I've circled it in red in the screenshot ...