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
20 views

Big-O Notation and showing algorithmic growth rate with witnesses?

I have been out of class sick for a week with the flu and am having some trouble getting caught up on our latest sections on Big-O notation. Can someone explain the following from the textbook to me? ...
9
votes
3answers
203 views

Finding where the tail starts for a probability distribution, from its generating function

Suppose we generate "random strings" over an $m$-letter alphabet, and look for the first occurrence of $k$ consecutive identical digits. I was with some effort able to find that the random variable ...
4
votes
1answer
388 views

Asymptotic error of Fourier series partial sum of sawtooth function

In Iwaniec's book, Topics in Classical Automorphic Forms, pg. 4, he gives the statement: $$\{x\}=\frac{1}{2}-\sum_{n=1}^N\frac{\sin 2\pi nx}{\pi n}+O((1+||x||N)^{-1})$$ where $\{x\}$ denotes the ...
1
vote
1answer
12 views

Asymptotic Relative Efficiency of Sample Mean and Median

I'm following some online lecture notes on AREs and don't understand where a certain value came from. Consider a distribution function $F$ with a density function $f$ symmetric about $\theta$. We're ...
0
votes
3answers
34 views

Show $\lim_\limits{n\rightarrow \infty} \sqrt{n}(|c+\frac{d}{\sqrt{n}}|-|c|) = d* sign(c)$

Consider the sequence of real numbers $\sqrt{n}\left(\left|c+\frac{d}{\sqrt{n}}\right|-|c|\right)$ with $c,d \in \mathbb{R}$ and $c\neq 0$. Could you help me to show that $$\lim_\limits{n\rightarrow ...
2
votes
2answers
61 views

Finding asymptotic relationship between: $\frac {\log n}{\log\log n} \overset{?} = (\log (n-\log n))$

Given $f(n)=\frac {\log n}{\log\log n} , g(n)= (\log (n-\log n))$, what is the relationship between them $f(n)=K (g(n))$ where "K" could be $\Omega,\Theta,O$ I thought of taking a log to both ...
0
votes
0answers
15 views

Show that the point of minimum of a random function is bounded in probability

Consider a sequence of random variables $X_n:\Omega \rightarrow \mathbb{R}^k$ defined on the probability space $(\Omega, \mathcal{F}, P)$. Consider a parameter $\theta \in \Theta \subseteq ...
1
vote
0answers
28 views

Instantaneous drift of a stochastic process

Let $\mu_t$ and $\sigma_t$ be strictly positive bounded predictable processes and $W_t$ a Wiener process. Consider for $\Delta>0$ $$ X_{\Delta} = ...
0
votes
2answers
45 views

Almost sure convergence along a subsequence implies convergence in probability over the whole sequence

Consider a sequence of real-valued random variables $\{X_n\}_n$ almost surely converging to a real-valued random variable $X$ along a subsequence $\{n_k\}_k \subseteq \mathbb{N}$: $X_{n_k} ...
25
votes
2answers
1k views

A (non-artificial) example of a ring without maximal ideals

As a brief overview of the below, I am asking for: An example of a ring with no maximal ideals that is not a zero ring. A proof (or counterexample) that $R:=C_0(\mathbb{R})/C_c(\mathbb{R})$ is a ...
1
vote
1answer
44 views

A didactic example of logarithmic measure

I've read that two mathematicians, in the recent past, studied limits as $X$ tends to infinite, like as $$\frac{1}{\log X}\sum_{x\leq X:\pi(x)<\int_{2}^x\frac{dt}{\log t}}\frac{1}{x},$$ where ...
0
votes
0answers
29 views

Asymptotics of $\sum_{x = 0}^{\alpha n} {n \choose x}$

Let $\alpha \in (0, 1)$. What is the asymptotic growth of the following function? $$\sum_{x = 0}^{\alpha n} {n \choose x}$$ I am aware that ${n \choose \alpha n}$ grows asymptotically as a ...
0
votes
1answer
44 views

What does the ' symbol mean in this context?

This pertains to an explanation of Big-O notation: If one pair of witnesses is found, then there are infinitely many pairs. We can always make the k or the C larger and still maintain the ...
0
votes
0answers
15 views

On an asymptotic recurrence

Fix $c\in\Bbb R$. Denote $A_0=M_0=n$. Consider $A_{i+1}=A_i+\lceil A_i^c\rceil$ and $M_{i+1}=M_i\times \lceil M_i^c\rceil$. How fast does $A_i$ grow for different ranges of $c$? $M_i$ grows as ...
2
votes
1answer
58 views

A strange identity related to the imaginary part of the Lambert-W function

Working on a problem in QFT, i was stumbeling about some expressions containing the Lambert-$W$ function. Playing around, i discovered experimentally that the following statement seems to be true ...
1
vote
0answers
53 views

Can you estimate the difference of primes between numerator and denominator?

Let $p_n$ the nth twin prime, it is $p_n$ is a prime number and $2+p_n$ is also a prime. It is well know that Brun's theorem states (unconditionally) that $$\mathcal{B}=\sum_{n\geq ...
1
vote
1answer
36 views

Show that $o(\frac{a_n}{n})+o(\frac{1}{n})+O(\frac{a_n^2}{n})=O(\frac{1}{na_n})$

Consider a sequence of real numbers $a_n$ such that $\lim_{n\rightarrow \infty}a_n=0$ and $\lim_{n \rightarrow \infty}na_n=\infty$. Could you help me to show that ...
9
votes
0answers
100 views

Eigenvalue problem for $−\psi''(x) − (ix)^ N \psi(x) = E\psi(x)$ in complex plane

To find the eigenvalue $E$ in the complex plane of $x$ for one dimensional Schrodinger equation $$ −\psi''(x) − (ix)^ N \psi(x) = E\psi(x). $$ where $N$ can be any real number, the boundary condition ...
1
vote
2answers
25 views

Big-oh and Small-oh Notation: Ratio.

Is it possible to say something about the order of ratios like $O(1/n^2)/o(1)$ or $O(1/n^2)/O(1/\sqrt{n})$?
7
votes
5answers
5k views

Simple proof of showing the Harmonic number $H_n = \Theta (\log n)$

Consider the partial sum of the divergent Harmonic series $H_n = \sum\limits_{k = 1}^{n}\frac{1}{k}$. I recently saw a question which required finding out the asymptotic bounds of $H_n$. Now, I could ...
4
votes
1answer
33 views

What about $\sum_{\substack{2\leq n\leq y,\text{n prime}}}n\log\log n$ when $y=[x]\to\infty$?

For a real $x\geq 2$ and when we take $y= [x]$ its integer part, I am trying to study the asymptotic size or growth of $$\sum_{\substack{2\leq n\leq y,\text{n prime}}}n\log\log n,$$ I believe that ...
0
votes
1answer
31 views

does $f(n) = O(g(n))$ implies $(f(n))^{log(n)} = O((g(n))^{log(n)}) ?$

if $f(n)$ and $ g(n)$ are monotonically increasing, and $f(n) = O(g(n))$. Does it imply that $(f(n))^{log(n)} = O((g(n))^{log(n)}) ?$ Well I had a go at it saying I need to show that ...
2
votes
4answers
49 views

Showing that Harmonic numbers are $\Theta(\log n)$, intuitively

I wish to verify that Harmonic numbers $H_n = \sum_{k=1}^{n} \frac{1}{k}$ are $\Theta(\log n)$. One idea I have is to approximate the sum with an integral: $$\int_{1}^{n} \frac{1}{k} ~dk = \log(n) - ...
1
vote
2answers
49 views

Big O notation: ratio of two $O(\cdot)$'s is $O(\cdot)$ of the ratio?

Is it true that if $f_1=O(g_1)$ and $f_2=O(g_2)$ then $$\frac{f_1}{f_2}=\frac{O(g_{1})}{O(g_{2})}=O\!\left(\frac{g_1}{g_2}\right)$$ ?
2
votes
0answers
44 views

Asymptotic behaviour of an integral depending on a parameter

I am trying to compute the asymptotics on $t$ of the following integral: \begin{equation} I(t)=\int_{\mathbb{R}^{n}}e^{-|\lambda|^{2}/2t}\prod_{i<j}\left( e^{\lambda_{j}/t}-e^{\lambda_{i}/t} ...
1
vote
0answers
34 views

Asymptotic sums and big-O notation

Suppose I have to compute the following asymptotic sum ($x\rightarrow\infty$): $$ S(x):=\sum_{n\leq f(x)} O(g(x,n))\;, $$ where the function $g(x,n)$ is non-decreasing in $n$, so that in our case ...
0
votes
1answer
45 views

Product of Two systems with the same asymptotically stable fixed points

I am trying to figure out the nature of a new dynamical system that is equal to the product of two dynamical systems with the same asymptotically stable fixed point. For instance, if i have $x' = ...
0
votes
1answer
13 views

How to get values of $n_0$ and $c$ for big-omega.

Let $f(n)=3n^3$ and $g(n) = n^3$ then $f = Ω(g)$ Answer: Let $n_0 = 0$ and $c = 1$ So I know how to find $c$ and $n_0$ for big-oh, like this: $3n^3 \leq cn^3$ [divide to be left with c] $= c ...
1
vote
0answers
29 views

Approximating $\prod_{r=s}^t (1-b/r)$

I am currently trying to place an order of precision on the approximation $$\prod_{r=s}^t \left(1-\frac{b}{r}\right) \approx \left(\frac{s}{t}\right)^b$$ This follows because $$\prod_{r=s}^t ...
0
votes
0answers
15 views

Derive the asymptotic distribution of $\frac{2}{n(n-1)}\sum\sum_{i<j}|X_{i}-X_{j}|$

Derive the asymptotic distribution of Gini's mean diference, which is defined as $\frac{2}{n(n-1)}\sum\sum_{i<j}|X_{i}-X_{j}|$. This is an exercise of Asyptotic Statistics by A.W. van der Vaart. I ...
0
votes
1answer
1k views

What is the computational complexity of a brute force perfect numbers finder algorithm?

A loop goes thru all numbers from one to N to find perfect numbers. For each number in the range, it checks all numbers less than it to see if it's a divisor by modding it by the number and checking ...
0
votes
0answers
15 views

mann's test for trend

To test the null hypothesis that a sample $X_{1},...,X_{n}$ is i.i.d. against the alternative hypothesis that the distributions of the $X_{i}$ are stochastically increasing in $i$. Mann suggested to ...
2
votes
2answers
22 views

Comparing the growth of two function by taking logarithms

I was trying to understand how to compare the big-O growth of two functions by taking the logarithm (or some increasing function like $\sqrt{f(n)}$. For example, take $2^{({log_2n})^2}$ vs $ ...
0
votes
1answer
25 views

Find the asymptotic solution $\Theta$ of the recurrence using the master theorem

I just took a quiz for an algorithms class that I didn't do so well on. It was on the master theorem. Unfortunately the professor refuses to supply answers or even tell me what I got wrong, so I was ...
0
votes
0answers
26 views

Growth rate of $\zeta(n)^{-1}$

What is the asymptotic growth rate of $\frac1{\zeta(n)}$? Is it polynomial in $n$?
2
votes
1answer
50 views

Master method and choosing $\epsilon$

I am reading CLRS3, currently Chapter 4 and Section 4.5, "The master method for solving recurrences." I understood what is the $\epsilon$ , but I can't understand why they choose $ \epsilon ...
0
votes
2answers
45 views

Prove or disprove that $\forall n \in N$ $, \, n! \in \mathcal{O}(2^n)$

Prove or disprove that $\forall n \in N$ $, \, n! \in \mathcal{O}(2^n)$ My attempt: $f(n) = n!$ $g(n) = 2^n$ First I checked if I needed to prove or disprove this statement, and to do so I ...
-1
votes
1answer
23 views

Asymptotic analysis : Theory

how do you prove that when the limit of n approaches towards positive infinity while n^2/(log n)! We tried to used Stirling theorem but this may not work due to the fact that it may or may not exist ...
0
votes
0answers
28 views

Asymptotic behavior of two functions

I have trouble figuring out the asymptotic behavior of two functions. If $f(n) = n \log n$, then what do we know about $f^{-1}(n)$? I.e. what is the asymptotic behavior of $g(n)$ such that $g(n) ...
0
votes
1answer
29 views

Solve the recurrence using the Master Theorem: $T(n) = 5T\left(\frac{n}{4}\right) + n\lg \lg n$

I am trying to solve the recurrence: $$ T(n) = 5T\left(\frac{n}{4}\right) + n\lg \lg n. $$ I tried to apply the Master Theorem but it didn't get me anywhere: $$ a=5,\; b=4\; \text{ and } f(n) = n\lg ...
0
votes
1answer
15 views

find the asymptotic upper bound

I need to find the asymptotic upper bounds in $O$ notation for $T(N)$ in two recurrences. Assuming that $T(N)$ is constant for sufficiently small $N$, I need to make the bounds as tight as possible. ...
2
votes
2answers
39 views

Proof based on definition of big-$O$

I want to prove that $n! = O(n^n)$ based on the definition of big-$O$. I find it pretty easy to show that $n! = O(n^n)$ by simply showing that $n (n-1) < n \cdot n \ldots$ etc. However I can't ...
0
votes
2answers
32 views

Prove or Disprove Θ

I want to prove or disprove that $3n^3 +n^2\log(n) = Θ(n^3)$. I'm aware that I will need to either prove or disprove both big-o and big-Ω to prove or disprove Θ. I am simply struggling to do so. Help ...
1
vote
2answers
71 views

Show that $1^k+2^k+\cdots+n^k$ is $\Omega (n^{k+1})$

...where k is a positive integer. The Big Oh case is not so hard. But how do I show that $1^k+2^k+\cdots+n^k$ is $\Omega (n^{k+1})$?
0
votes
1answer
40 views

Prove that $\sum_{i=0}^{k} \lg \frac{n}{2^i} = \Theta(\lg^2 n)$

Show that if $n$ is a power of $2$, say $n = 2^k$, then we have the equality $\sum_{i=0}^{k} \lg \frac{n}{2^i} = \Theta(\lg^2 n)$. The first step is to prove $O(\lg^2n)$: $$ \lg \frac{2^k}{2^0} + \lg ...
0
votes
0answers
20 views

Can you analyze this identity involving the sum of divisors function and $rad(n)=\prod_{p\mid n}p$?

Let $\sigma(n)$ the sum of divisors function, then by Mobius inversion formula $$\sigma(n)=n-\sum_{\substack{d\mid n,d<n}}\sigma(d)\mu\left(\frac{n}{d}\right),$$ and since this function is ...
1
vote
1answer
33 views

Showing that $\log{\log^d{3n}} = O(\log{\log^d{n}})$

I'm trying to show this: $$\log{\log^d{3n}} \leq q\cdot \log{\log^d{n}} \;\;\exists\, q,k > 0,\forall n>k, \text{where } d \text{ is a constant} > 0$$ This is what I have so far ...
1
vote
1answer
18 views

$a_n\geq b_n$ for $n>\bar{n}$ implies $\limsup_{n\rightarrow \infty}a_n\geq \limsup_{n\rightarrow \infty}b_n$

Consider two sequences of real numbers $\{a_n\}_n, \{b_n\}_n$. I know that if $a_n\geq b_n$ $\forall n$ then $\limsup_{n\rightarrow \infty}a_n\geq \limsup_{n\rightarrow \infty}b_n$. Suppose ...
2
votes
2answers
43 views

Can you get a closed-form for $\sum_{j=0}^{\infty}\frac{2^{2j-1}B_{2j}}{(2j)!}$?

Let $B_{k}$ the kth Bernoulli number, then using their asymptotic I can justify the absolute convergence of this series $$\sum_{j=0}^{\infty}\frac{2^{2j-1}B_{2j}}{(2j)!},$$ since, if there are no ...
1
vote
0answers
49 views

Big-Theta - asymptotic bound - is solution sufficient enough?

I am wondering is my solution sufficient enough (or detailed enough) for the following question? or it is even a valid solution? Question: Find a tight asymptotic bound ($\Theta$) in terms of the ...