# Tagged Questions

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

2answers
22 views

### Find the minimum value of $n$ such that $\sin^n(c)<\varepsilon$ for some small constant $\varepsilon>0$

Let $c$ be a constant such that $0 <c \le \pi/2$ and $\sin(c) \ne 0$. Question: What is the minimum value of $n$ such that $\sin^n(c)< \varepsilon$ for some small constant $\varepsilon >0$ ? ...
1answer
27 views

### asymptotic complexity of functions

I'm curious if my asymptotic analysis of these functions are correct. I know the process is to strip the constants and then get to where its just comparing functions and taking limit to infinite and ...
1answer
80 views

### Why does Titchmarsh say that we can move the derivative under $\frac{2}{\pi}\int_0^\infty \frac{\Xi(t)}{t^2 + \frac{1}{4}} \cosh(\alpha t) \, dt$

If we define the Riemann-Xi function as $$\Xi(t) = \xi(\frac{1}{2} + it)$$ where $$\xi(s) = \frac{1}{2}s(s-1)\pi^{-\frac{s}{2}}\Gamma(\frac{s}{2})\zeta(s),$$ then according to Titchmarsh in his ...
1answer
45 views

1answer
132 views

### Asymptotic behavior of the zeros of the digamma function

The gamma function has just one extremum on each interval $(k,k+1)$, where $k$ is a negative integer. These extrema occur at the zeros of the derivative of the gamma function. Let $z_n$ denote the $n$-...
0answers
29 views

0answers
34 views

### How would you prove this Big Omega complexity?

We're given $f(n)=\frac{1}{5}n^2-30n-5$ and $g(n)=n^2$, and are asked to prove $f \in \Omega(g)$. The exercise was posted, but no solution is given (this is not an assignment question). So by ...
7answers
482 views

### Is it true that $2^n$ is $O(n!)$?

I had a similar problem to this saying: Is it true that $n!$ is $O(2^n)$? I got that to be false because if we look at the dominant power of $n!$ it results in $n^n$. So because the base numbers are ...
0answers
39 views

### Applying function to both sides of asymptotic expression

I apologize in advance if this has been asked elsewhere, but I couldn't find it. This seems like it should be a pretty simple question, but I'm drawing a blank. If you know that $f(x) \sim g(x)$, ...
3answers
82 views

### Big-O notation examples

How do I get c = 4 and n0 = 21, I understand that I could plug in different numbers till f(n) ≤ c * n for all n ≥ n0, but using f(n) how do I arrive at those numbers? ...
1answer
167 views

### Counting Primitive Operations

This is the solution I've been given for counting primitive Operation in an algorithm. I think I have my head around how all the operations are found, for instance the 2(n-1), the 2 is the primitive ...
1answer
41 views

### Number of rationals with denominator less than $N$

This is probably a duplicate since it seems like elementary number theory, but didn't find it after a cursory search. Let $r(N)$ be the number of rationals in $[0,1]$ with denominator less than or ...
2answers
57 views

### Order estimates question and big O notation

How can I show that $y(x) = 1 - \cos(x)$ is $\mathcal{O}(x^2)$ for $|x| <<1$ ? Additionally, with the $|x| << 1$ is there a precise definition? I tried to google it but nothing conclusive ...
0answers
28 views

### Asymptotic expansion of integrals of the form $\int_{\mathcal{D}} \exp(\lambda\, \phi(x))\, g(x) \,dx$ for small $\lambda.$

In the limit $\lambda\to\infty$ the asymptotic expansion of integrals of the form $\int_{\mathcal{D}}\exp(\lambda\,\phi(x))\,g(x)\,dx$ (where $\mathcal{D}\subseteq \mathbb{R^n}$ denotes the domain of ...
2answers
219 views

### Big O notation and limits

I'm wanting to take the $\lim_{x\to \infty} \frac {O(1)}{x^s}$, where $O(1)$ is Big O notation and $s>1$. I can see that it will be zero but I'm wanting to do it somewhat rigorously. Can I take the ...
0answers
52 views

0answers
107 views

### Asymptotic expansion of a Laplace-type integral with a “manifold of maxima”

Consider the integral $$I(\alpha)=\int_0^1 dx_1 \int_0^1 dy_1\int_{x_1}^1dx_2\int_{y_1}^1dy_2\,e^{-\alpha(x_2-x_1)(y_2-y_1)}$$ in the limit $\alpha\rightarrow\infty$. To find the asymptotic ...
0answers
216 views

### Asymptotic large order approximation for Bessel function expression

How does one find the asymptotic large order approximation for $\sup_{0\le x\le\infty} \left(\sqrt{x} J_n(x)\right)$, where $J_n$ is the Bessel function of the first kind and order $n$. This is NOT a ...
1answer
144 views

### Growth of $n!!\dots !$

The asymptotic growth of the factorial function $n!$ is famously given by Stirling's formula as $$n! \sim \sqrt{2 \pi n}\left(\frac{n}{e}\right)^n$$ Is there a similar formula for the iterated ...
1answer
133 views

### Suppose that $f (x)$ is $O(g(x))$. Does it follow that $2^{f(x)}$ is $O(2^{g(x)})$?

Suppose that $f(x)$ is $O(g(x))$. Does it follow that ? First, I start from for some $c$ is a real number. Then, I find . But, if i start from , I just find . I confused with that different form.
0answers
22 views

### How to do this asymptotic task?

Let a(n) be the amount of natural numbers, which are smaller than n, and their prime divisors are only 2 and 3. For example: 6 is good, because it only has 2 and 3 has prime divisors, but 10 is not ...
1answer
80 views

### Suppose that $f (x) =O(g(x))$. Does it follow that $\log |f (x)| =O(log |g(x)|)$?

Suppose that $f(x)=O(g(x))$. Does it follow that $\log |f (x)|=O(log |g(x)|)$? I start from $f(x)=O(g(x))$, until I get Does it mean $\log |f (x)|=O(log |g(x)|)$?
1answer
83 views

### How to solve this recurrence, $T(n) = T(\sqrt{n}) + n$ using recursive tree method?

How to solve this recurrence, $T(n) = T(\sqrt{n}) + n$ using recursive tree method? I draw the tree and got a sum, $T(n) = T(1) + ( n + n^{\frac 12} +n^{\frac 14}+n^{\frac 18}+\ldots +1)$ I need ...
2answers
53 views

### How to prove that $2^{n+1} = \Theta(2^n)$?

I have a problem were I need to prove big theta. $f(n) = 2^{n+1} = Θ(2^n)$. I proved that this was true for big O but I'm not sure how to go about proving big Theta.
4answers
59 views

### Does the inequality $n! > A \cdot B^{2n+1}$ hold for sufficiently large $n$?

Suppose $A,B >0$ are given constants. Is it possible to find a large enough $n \in \mathbb{N}$ such that $$n! > A \cdot B^{2n+1}?$$
0answers
44 views

### Proof $\mathcal{O}(f(n)) = \mathcal{O}(g(n)) \iff f(n) \in O(g(n)) \land g(n) \in \mathcal{O}(f(n))$

There is an exercise that ask me to prove this logic formula about the complexity of algorithms: $\mathcal{O}(f(n)) = \mathcal{O}(g(n)) \iff f(n) \in O(g(n)) \land g(n) \in \mathcal{O}(f(n))$ Proof:...
2answers
22 views

2answers
262 views

3answers
69 views

### Prove line asymptotic to curve

I have a function denoted as: $f(x) = \frac{x}{1+e^\frac{1}{x}}$ I want to prove the line: $g(x)= \frac{x}{2} - \frac{1}{4}$ Is asymptotic (slant asymptote) to the above function when approaching ...
3answers
77 views

### Asymptotic notation (big Theta)

I'm currently in the process of analyzing runtimes for some given code (Karatsuba-ofman algorithm). I'm wondering if I'm correct in saying that $\Theta(\left\lceil n/2\right\rceil) + \Theta(n)$ is ...
1answer
92 views

### Big-theta notation

I was wondering about big-theta ($\Theta$) notation. A) Is $\Theta(n/2) \leq \Theta(n)$ for $n$ being an integer? I know that $n/2 = O(n)$, but does it also mean that $\Theta(n/2) \leq \Theta(n)$? ...
3answers
84 views

### Lower bound for the falling factorial $(2n)_{n}$

I'm looking for a lower bound for the falling factorial $$(2n)_{n}:= \frac{(2n)!}{n!}$$ I saw on Wikipedia that $n! > \sqrt{2{\pi}n}(\frac{n}{e})^n$ . So I assume that a possible lower bound ...
1answer
58 views

### Dealing with floor function in binomial coefficients

I'm trying to estimate $\binom{n}{\left \lfloor{\alpha n}\right \rfloor }$ asymptotically using Stirling's formula. However, I'm a little lost with what to do about the floor function here. In the ...
1answer
99 views

### Stuttering Subsequence Problem - Explain the example

I'm reading an article that deals with solving the stuttering subsequence problem in $\Theta (n)$. The article can be found here: http://www.cse.yorku.ca/~andy/pubs/Stutter.pdf Some background on ...
3answers
48 views

### Why does $\lim_{ t\to 0} \frac{o(t^2)}{t} = 0$?

Why does $\lim_{ t\to 0} \frac{o(t^2)}{t} = 0$? $\sqrt t = o(t^2) \implies \lim_{t\to 0} \frac{\sqrt t}{t} = \infty$ Maybe I don't understand completely the little-o notation.
1answer
47 views

### I need to show the following two limits

First, for $a>-1$: $$\lim_{n\to\infty}\frac{a+1}{n^{a+1}}\sum_{j=1}^nj^a = 1$$ Second, for $p>0$: $$\lim_{n\to\infty}\frac{e^a-1}{e^{a(n+1)}}\sum_{j=1}^ne^{aj} = 1$$ In particular, why do we ...