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
1answer
62 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 ...
1
vote
1answer
22 views

limiting variances of iid sample mean

In the book Statistical Inference (George Casella 2nd ed.), page 470, there is an example: $\bar{X}_n$ is the mean of $n$ iid observations, and E$X=\mu$, $\operatorname{Var}X=\sigma^2$. "If we take ...
1
vote
1answer
71 views

Is it possible to find the least common divisor of a two numbers that are not relatively prime in polynomial time?

As the question states: Is it possible to find the least common divisor of two number that are not relatively prime in polynomial time? If so, how? Thanks!
3
votes
0answers
36 views

Merten's function

I am tasked with applying the Wiener-Ikehara Theorem to achieve a bound of little o(x) on Merten's function $\sum_{n=1}^x \mu (n)$. My problem is the Wiener-Ikehara Theorem applies to Dirichlet series ...
0
votes
2answers
35 views
1
vote
0answers
38 views

Asymptotic Proof

Can someone explain this asymptotic proof to me.I am stuck at the inductive step and get lost around this step $2 × n! < (n + 1) × n!$ $$2n = o(n!)$$ True Proof: In order to $2n = o(n!)$ be true, ...
2
votes
1answer
58 views

How to find $s(\exp(d(x)))$ ~ $ x + 2 $?

Let $x$ be a positive real. I want to find a pair of analytic functions $s(x),d(x)$ such that $s(d(x)) = x$ and $ s(\exp(d(x)))$ ~ $ x + 2 $ More presicely I Also want : $$ \lim_{x \to \infty} ...
2
votes
2answers
21 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$ ? ...
0
votes
1answer
22 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 ...
3
votes
2answers
96 views

Asymptotic Behaviour Of $\frac{1}{x-1}+\frac{1}{x^2-1}+\frac{1}{x^3-1} + \cdots$ as $x \to 1 $

I define $$ f(x) = \sum_{n=1}^{\infty} \frac{1}{x^n-1} = \frac{1}{x-1} + \frac{1}{x^2-1} + \frac{1}{x^3-1} +\frac{1}{x^4-1} + \frac{1}{x^5-1} + \cdots$$ and I then wish to study the asymptotic ...
0
votes
1answer
31 views

Design an algorithm - Median, computer science

I was wondering if this question belongs here or on StackOverflow, but it is a question of mathematical nature so this seems more appropriate. We have an array $S$ of $n$ different numbers ...
6
votes
2answers
36 views

If $f(n)$ is $O(g(n))$ and $g(n)$ is $O(f(n))$, is $f(n) = g(n)$?

Question: If $f(n)$ is $O(g(n))$ and $g(n)$ is $O(f(n))$, is $f(n) = g(n)$? I'm studying for a discrete mathematics test, and I'm not sure if this is true or false. Since Big-OH ignores constant ...
1
vote
1answer
45 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 ...
1
vote
0answers
40 views

Summation involving digamma and floor functions

I am trying to find an asymptotic expansion for the following sum: $$\sum_{n=1}^K \frac{\phi_0( 1/2+n+\lfloor(2n-1)/\sqrt{2}\rfloor)}{(4n-2)}$$ where $\phi_0$ is the digamma function and $\lfloor ...
2
votes
0answers
26 views

Asymptotic solution to $m \leqslant e^{\lambda t} (c t^q - \varepsilon)$

What is the smallest $t$ statisfying the inequality: $m \leqslant e^{\lambda t} (c t^q - \varepsilon)$, where $\varepsilon$ is arbitrary small positive number? I believe $t$ must be of the from: $$t = ...
2
votes
0answers
39 views

Asymptotic behavior of $1/(a^2+\epsilon^2)$ as $\epsilon\to0$

A limit that often arises in physics is $$ \lim_{\epsilon \to 0} \frac{ \epsilon }{ a^2 + \epsilon^2 } = \pi \delta(a) ............ (1) $$ Is there a similar sort of limit for $$ \lim_{\epsilon \to 0} ...
0
votes
0answers
25 views

Asymptotic analysis of $\int_{0}^{\infty} \frac{\sqrt k J^2_{\ell}(k) \sin{(\tau\sqrt k)}}{(k+1/2)^{n+2}} dk$

Question as the title showed, in which $n$ and $\ell$ are positive integers, $\tau$ is real number and $J$ means Bessel functions. How to do the asymptotic analysis when $\tau$ approaches zero? Any ...
2
votes
1answer
35 views

Simple vs compound interest rates and Taylor expansion

I am having trouble deciphering a portion from my finance text. Let $i = \text{interest rate}$, $n = \text{Some arbitrary time period}$ and $C = \text{Cash invested}$ And also $C(1+i)^n$ ...
6
votes
3answers
157 views

Aproximation of $a_n$ where $a_{n+1}=a_n+\sqrt {a_n}$

Let $a_1=2$ and we define $a_{n+1}=a_n+\sqrt {a_n},n\geq 1$. Is it possible to get a good aproximation of the $n$th term $a_n$? The first terms are $2,2+\sqrt{2}$, $2+\sqrt{2}+\sqrt{2+\sqrt{2}}$ ... ...
3
votes
1answer
41 views

Prove that $3\log n$ is $O(\exp(0.001n))$

First time posting here. Hi math stack-exchange community! I have a bonus question on my assignment and I am having trouble proving it. The main reason is that I am only limited to using the rules ...
3
votes
3answers
43 views

Rule for calculating big-O plus example I can't figure out

I have the following rule: If $f$ is $O(g)$ for ${x\to\infty}$ and $\lim_{x\to\infty}g(x) = 0$ than also $\lim_{x\to\infty}f(x) = 0$ Then my text proceeds to give an example: ...
2
votes
3answers
42 views

Proving that $2n^2 + n + 1 = O(n^2)$ and big O proofs in general

Alright so here's the thing, I'm in a class in Computer Science called Algorithm Analysis and it is required for me to learn Big O, Big Omega, etc. While I sort of understand what this is for, I still ...
1
vote
0answers
27 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 ...
2
votes
1answer
17 views

Estimate of tails of sums of reciprocals of a bit more than powers

The tails of sums of reciprocal powers have nice estimates: For $\alpha>1$ the integral test gives $$ \sum_{n=j}^\infty \frac{1}{n^\alpha} \leq \int_{j-1}^\infty \frac{1}{x^\alpha} dx = ...
1
vote
0answers
29 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 ...
4
votes
7answers
447 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 ...
3
votes
0answers
36 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)$, ...
1
vote
3answers
56 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? ...
12
votes
2answers
248 views

When is this sum of perfect powers bounded

For any positive integers $n,d$, let $$ A_d(n)=\frac{\sum_{k=1}^n k^{2d}}{n(n+1)(2n+1)} $$ It is easy to see (and well-known) that for fixed $d$, $A_d(.)$ is a polynomial of degree $2d-2$. Writing ...
1
vote
2answers
51 views

Probability that colored balls are separated

Say we throw $b$ blue balls and $r$ red balls uniformly into $n$ boxes. The probability that no box contains a red as well as a blue ball is then, by the inclusion exclusion principle: $$p = ...
0
votes
1answer
22 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 ...
1
vote
1answer
125 views

Theta notation from $\DeclareMathOperator{\lg}{lg}$the inequality $c_1\lg(n) \leq \lg(k) \leq c_2\lg(n)$

Consider the inequality $$ c_1\lg(n) \leq \lg(k) \leq c_2\lg(n),\text{ for } n \geq n_{0} $$ With $c_1,c_2,n_0 > 0$, $\lg(k) = \Theta(\lg(n))$ By deriving the actual relationship of $k$ with ...
1
vote
0answers
54 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 ...
0
votes
0answers
28 views

How to study the asymptotic behavior of $f(r)=\int_0^1 dx\, \text{Li}_2\Big(1-\frac{r}{x(1-x)}\Big)$ for small $r$?

How does one study the asymptotic behavior of the integral $$f(r)=\int_0^1 dx\, \text{Li}_2\Big(1-\frac{r}{x(1-x)}\Big)$$ as $r\rightarrow0$ from positive values? Here $\text{Li}_2$ is the ...
1
vote
2answers
80 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 ...
0
votes
1answer
28 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 ...
2
votes
2answers
50 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 ...
0
votes
0answers
34 views

$f(n)=3f(\frac{n}{3})+O(logn)$

I was asked to figure out the time complexity analysis for the following recurrence relation: $f(n)=3f(\frac{n}{3})+O(logn)$ I worked it out as O(nlgn), Would like to know if this is right or ...
1
vote
0answers
22 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 ...
0
votes
2answers
36 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 ...
0
votes
1answer
27 views

Show a function similar to $(1/x)lnx$ becomes small as x grows

I am tasked with showing that, for $l \gg k$, $$ t = \frac{1}{l-k}\ln(l/k) $$ is small (it is given that $t$ is positive). Intuitively, this seems correct because it is 'similar' to $$ \frac{1}{x} ...
1
vote
0answers
46 views

Proving $n^{10\log(n)} = O((\log^n(n))$

I need to decide which of the following is correct: $n^{10\log(n)} = O((\log^n(n))$ $n^{10\log(n)} = \Theta((\log^n(n))$ $n^{10\log(n)} = \Omega((\log^n(n))$ So I'm saying $n^{10\log(n)} = ...
0
votes
0answers
13 views

Question about big omega proof

I'm not sure if I should post it here or in StackOverflow, but anyway... Prove that: $n^5-2\log{n}=\Omega{(n^5)}$. Proof: We need to find $c, n_0 \geq0$ such that, for all $n \geq n_0$, ...
4
votes
0answers
66 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 ...
0
votes
1answer
27 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.
1
vote
1answer
97 views

Expectation and Variance of random walks

Consider random walks of fixed length (e.g. $5$) starting at node $u$ in an undirected and connected graph with $N$ vertices. If a node $k$ has $N_k$ edges, the probability of the walk reaching any of ...
0
votes
0answers
20 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 ...
1
vote
1answer
28 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)|)$?
0
votes
0answers
21 views

Non-deterministic multiplication algorithms

Are there any algorithms for non-deterministic Turing machines that can compute the decision problem $mn=x$ (where $m=O(n),x=O(n^2)$) faster than the equivalent deterministic algorithm? Equivalently, ...
0
votes
1answer
38 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 ...