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
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
100 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
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 $$
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": ...
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
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 ...
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 ...
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
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$ ...
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 ...
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
33 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 ...
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 ...
0
votes
3answers
114 views

Prove that a circle has an infinite number of tangents

It seems obvious that a circle is comprised of the set of all points that are equidistant from one point, and that each point on the circumference of the circle represents a tangent. This seems to ...
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 ...
7
votes
1answer
94 views

Help proving $\sum_{n\le x}{\ln{n}}=x\ln{x}-x+O(\ln{x})$

Just learning a bit about big O notation and have come across this exercise. The notation used is $$\sum_{n\le x}{\ln{n}}=x\ln{x}-x+O(\ln{x})$$ and I am assuming that is equivalent to ...
5
votes
1answer
113 views

Asymptotics of an oscillatory integral with a linear oscillator

I am interested in asymptotic results for $$ S(p) = \int_0^1 \frac{y \sqrt{1-y^2}}{(\varepsilon^2-1)y^2+1} \sin(py) dy, $$ i.e. a result that is valid as $p\rightarrow\infty$. The parameter ...
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 ...
9
votes
1answer
232 views

Analytic number theory primer — sequences and series

For a book like Titchmarsh, or Iwaniec and Kowalski, it seems a thorough knowledge of asymptotics is a prerequisite. What are good books for training oneself in such manipulation of asymptotics, ...
4
votes
2answers
108 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 ...
1
vote
1answer
47 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 ...
3
votes
2answers
81 views

Integration by expansion

Consider the integral \begin{equation} I(x)= \frac{1}{\pi} \int^{\pi}_{0} \sin(x\sin t) \,dt \end{equation} show that \begin{equation} I(x)= \frac{2x}{\pi} +O(x^{3}) \end{equation} as ...
1
vote
1answer
34 views

How to find an asymptotic formula for $f(n)=\sum_{k=1620}^{n}(\log\log\log k)^{2}$?

How to find an asymptotic formula for function given below. $$f(n)=\sum_{k=1620}^{n}(\log\log\log k)^{2}$$
1
vote
1answer
23 views

Estimation higher order

Consider non-dimensional differential equation for the height at the highest point is given by \begin{equation} h(\mu)= \frac{1}{\mu}- \frac{1}{\mu^2} \log_e(1+\mu) \end{equation} $0<\mu\ll 1.$ ...
0
votes
2answers
504 views

Ratios in big-O notation?

Hi can anyone give me a counter example of the following claim: f(n) = O(s(n)) and g(n)=O(r(n)) imply f(n)/g(n) = O(s(n)/r(n)) Thank you
0
votes
3answers
39 views

Big O question related to nested loop

So i have code that is a nested loop and the outside loop executes n times but the inside loop executes $n\sqrt{n}$ times. So would my worst case scenario still be $O(n^2)$?
3
votes
2answers
150 views

Big O and function composition

On the last page of this document, a property of Big O operations is listed which says that if $f_1(n)$ = O($g_1(n)$) and $f_2(n)$ = O($g_2(n)$) then $f_1$o $f_2$ = O($g_1$ o $g_2$) Why is ...
0
votes
1answer
51 views

Laplace's Method Integration

Consider the integral \begin{equation} I_n(x)=\int^2_1 (\log_{e}t) e^{-x(t-1)^{n}} \, dt \end{equation} Use Laplace's Method to show that \begin{equation} I_n(x) \sim \frac{1}{nx^\frac{2}{n}} ...
0
votes
1answer
115 views

Prove that there exists a constant $C$ such that $[z^n]\exp(z/(1-z)) = O(\exp(C\sqrt{n})) $ [closed]

Prove that there exists a constant $C$ such that: $$[z^n]\exp(z/(1-z)) = O(\exp(C\sqrt{n})).$$ The bound of $z$ is $\vert z \vert<\frac14$
0
votes
1answer
56 views

Laplace's Method (Integration)

Consider the integral \begin{equation} I(x)=\int^{2}_{0} (1+t) \exp\left(x\cos\left(\frac{\pi(t-1)}{2}\right)\right) dt \end{equation} Use Laplace's Method to show that \begin{equation} I(x) \sim ...
3
votes
0answers
65 views

Saddle point method: a rigorous proof?

I am trying to prove in a fully rigorous way the Saddle Point method for holomorphic functions of 1 complex variable. In books I find only complicated general statements or non-rigorous proofs. Hence ...
0
votes
1answer
51 views

Expansion of Integration

Consider the integral \begin{equation} I(x)=\int^{2}_{0} (1+t) \exp\left(x\cos\left(\frac{\pi(t-1)}{2}\right)\right) dt \end{equation} show that \begin{equation} I(x)= 4+ \frac{8}{\pi}x +O(x^{2}) ...
3
votes
1answer
2k views

how can be prove that $\max(f(n),g(n)) = \Theta(f(n)+g(n))$

how can be prove that $\max(f(n),g(n)) = \Theta(f(n)+g(n))$ though the big O case is simple since $\max(f(n),g(n)) \leq f(n)+g(n)$ edit : where $f(n)$ and $g(n)$ are asymptotically nonnegative ...
1
vote
1answer
31 views

How do you define computational complexity abstractly?

Let the problem we're studying be $f : X \to Y$. Say, I don't know what I want to define time-complexity with respect to, I just know I have a map $|\cdot| : X \to \Bbb{R}$, such that $|\cdot| \geq ...
3
votes
2answers
52 views

Short argument for asymptotic value of parameter integral

I want to find the main term of the asymptotic expansion for $x\to 0^+$ for $$f(x)=\int_0^{\pi/2} \dfrac{\cos t}{t+x}dt.$$ Now, clearly, the problem is at $t=0$ and the cosine is almost $1$ ...
0
votes
2answers
39 views

Discrete Mathematics: Prove that f(x) is in O(x)

Prove that $$\frac{2x^{2}+x}{x+1}$$ is in $O(x)$
1
vote
1answer
820 views

Solving a recurrence realtion using backward substitution.

So I've been trying my best to do this, and I have made some good progress, I just need to know if what I have done is correct and if not, what the hell am I doing wrong? :P I start off with this ...
2
votes
4answers
504 views

Prove that $3^n$ is not $O(2^n)$

I have this question in my assignment. I need to prove, using only the definition of $O(\cdot)$, that $3^n$ is not $O(2^n)$. It is obviously true for any $n \geq 1$. To prove $3^n \in O(2^n)$, we ...
2
votes
1answer
47 views

asymptotics of this sum $ x \to 0 $

given the sum $$ \sum_{n=0}^\infty \frac{\exp(-nx)}{n+a} =f(x) $$ what would be the asymtptic of this series ?? for $a=1$ i believe this series goes as $ f(x) \sim \frac{1}{x}+ \gamma $ for every ...
1
vote
1answer
82 views

What is $O\Big((n+1)!\Big)$?

What is $f(n) = (n+1)!$ which is also $f(n) = (n+1)n!$ in terms of big-O notation? My guess is $O(n \cdot n!)$ but I am not sure. I only know it is certainly $f(n) \in O(n^n)$.
3
votes
2answers
225 views

The geometric mean of primes less than or equal to $x$

I want to show that the limit of the geometric mean of primes less than or equal to $x$ is $e$ as $x \to \infty$. Is this correct? Using the product law of logarithms we have $$\ln \prod\limits_{p ...
1
vote
1answer
62 views

Bound summation of successive square roots

What is a tight upper bound for $f(n)$ where $f(n) = f(\sqrt{n}) + \frac{1}{n}$. One can easily find the following upper bound $O(\lg \lg n)$, however I'm interested in a tight bound. Regards.
1
vote
0answers
79 views

“Balancing” two infinities

Given these two computational complexities of 2 algorithms: $\exp(O(\sqrt{\log n \log \log n}))$ $O(\sqrt{\exp n} / \log{ \sqrt{ \exp n} })$ where I imagine the first one goes to infinity slower ...
1
vote
0answers
71 views

Big-O Notation for remainder terms in Taylor expansion

The Big-O notation is commonly used in Taylor expansions of the form $$f(x+\epsilon)=f(x)+\epsilon f'(x)+O(\epsilon^2)$$ to say that the remainder term grows at least quadratic around $\epsilon=0$. ...
0
votes
2answers
22 views

Big Omega — n, n + 100

Given $f(n) = n$ and $g(n) = n + 100$, it seems that f(n) is $O(g(n))$ when $C = 1$ and $k= 0$. That is, for every $n$ from $0$ to infinity, g(n) is strictly larger than f(n). Now, concerning ...
1
vote
1answer
53 views

Prove or disprove: $(\frac{1}{n})^n(1 - \frac{1}{n})^{n^2-n} \simeq \frac{1}{n!}$ as $n \rightarrow \infty$.

Prove or disprove: $(\frac{1}{n})^n(1 - \frac{1}{n})^{n^2-n} \simeq \frac{1}{n!}$ as $n \rightarrow \infty$. I'm trying to prove the statement by building on my observation that $(1-\frac{1}{n})^n$ ...
2
votes
1answer
31 views

Big O notation preserved under convex functions?

Suppose that the random variable $X_T$ is $O_p(1)$ as $T \rightarrow \infty$, i.e. $\forall \epsilon>0$, $\exists M_\epsilon>0$ such that $\mathbb{P}(X_T>M_\epsilon)<\epsilon$ $\forall T$. ...
3
votes
0answers
113 views

Question about Big O notation for asymptotic behavior in convergent power series

Examples of such use of Big O notation can be found for instance on Wolfram Alpha here. More details on the Wikipedia page. The idea, as I understand it, is that the term between parenthesis in Big O ...